luogu2038 [NOIp2014]无线网络发射器选址 (前缀和)

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define CLR(a,x) memset(a,x,sizeof(a))
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=150;
 7 
 8 inline ll rd(){
 9     ll x=0;char c=getchar();int neg=1;
10     while(c<‘0‘||c>‘9‘){if(c==‘-‘) neg=-1;c=getchar();}
11     while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar();
12     return x*neg;
13 }
14 
15 int d,N;
16 ll sum[maxn][maxn];
17 
18 int main(){
19     int i,j,k;
20     d=rd(),N=rd();
21     for(i=1;i<=N;i++){
22         int a=rd(),b=rd(),c=rd();
23         sum[a][b]=c;
24     }
25     for(i=0;i<=128;i++){
26         for(j=0;j<=128;j++){
27             sum[i][j]+=(i?sum[i-1][j]:0)+(j?sum[i][j-1]:0)-(i&&j?sum[i-1][j-1]:0);
28         }
29     }
30     ll mm=0;int cnt=0;
31     for(i=0;i<=128;i++){
32         for(j=0;j<=128;j++){
33             int i0=max(0,i-d),j0=max(0,j-d),ii=min(128,i+d),jj=min(128,j+d);
34             ll x=sum[ii][jj]-(j0?sum[ii][j0-1]:0)-(i0?sum[i0-1][jj]:0)+(i0&&j0?sum[i0-1][j0-1]:0);
35             if(x>mm) mm=x,cnt=1;
36             else if(x==mm) cnt++;
37         }
38     }
39     printf("%d %lld\n",cnt,mm);
40     return 0;
41 }