UVA 10827 Maximum sum on a torus

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 #define REP(i,n) for(int i=0; i<(n); i++)
 8 #define FOR(i,s,t) for(int i=(s); i<=t; i++)
 9 typedef long long ll;
10 const int INF = 1<<30;
11 const int N = 155;
12 int S[N][N],n,_;
13 int sum[N];
14 
15 void show(){
16     FOR(i,1,2*n){
17         FOR(j,1,2*n)
18             printf("%4d",S[i][j]);
19         cout<<endl;
20     }
21 }
22 
23 void solve(){
24     scanf("%d", &n);
25 
26     //矩阵扩大
27     FOR(i,1,n) FOR(j,1,n){
28          scanf("%d", &S[i][j]);
29          S[i+n][j] = S[i][j];
30          S[i][j] += S[i-1][j];
31          S[i][j+n] = S[i][j];
32 
33     }
34     FOR(i,n+1,2*n) FOR(j,1,n){
35         S[i][j] += S[i-1][j];
36         S[i][j+n] = S[i][j];
37     }
38 
39     int ans = -INF;
40     FOR(i,0,n) FOR(j,i+1,i+n){//枚举上下边界，从右往左扫描
41          int q[N<<1],head=0,tail=0;
42          for(int k = 1; k<2*n; k++){
43              sum[k] =S[j][k] - S[i][k] + sum[k-1];
44              while(tail>head && sum[k] <= sum[q[tail]]) tail--;//用单调队列优化
45              q[++tail] = k;
46              while(tail>head && k - q[head+1]>n) head++;
47              ans  = max(ans , sum[k] - sum[q[head+1]]);
48          }
49     }
50     printf("%d\n",ans);
51 }
52 
53 int main(){
54 //    freopen("in.txt","r",stdin);
55     scanf("%d", &_);
56     while(_--) solve();
57     return 0;
58 }