View Code of Problem 182

#include<stdio.h>
#define maxn 105
typedef long long ll;
int size,num[maxn][maxn];
ll sum[maxn][maxn],dp[maxn][maxn][maxn];
ll ans = -111111,max;
void getsum()
{
    int i,j,k;
   for(j = 0;j < size;j ++)
    sum[j][0] = 0;
   for(i = 1;i <= size;i ++)
   {
       for(j = 1;j <= size;j ++){
            sum[i][j] = sum[i][j-1] + num[i][j];
            /*printf("%lld\n",sum[i][j]);*/
       }
   }
   max = dp[1][1][1];
   for(k = 1;k <= size;k ++)
   {
       for(i = 1;i <= size;i ++)
            for(j = i;j <= size;j ++){
                dp[k][i][j] = sum[k][j] - sum[k][i-1];
                if(sum[i][j] > max) max = dp[k][i][j];
                /*printf("%lld ",dp[k][i][j]);*/
            }
    /*printf("\n");*/
   }
}
void solve()
{
    int i,j,k;
    ll tmax = 0;
    ans = 0;
    for(i = 1;i <= size;i ++){
        for(j = i;j <=size;j ++){
            tmax = 0;
            for(k = 1;k <= size;k ++)
            {
                if(tmax + dp[k][i][j] > ans) {ans = dp[k][i][j] + tmax;}
                if(tmax + dp[k][i][j] > 0) {tmax = tmax + dp[k][i][j];}
                else tmax = 0;
            }
        }
    }
    printf("%lld\n",ans);
}
int main(void)
{
    scanf("%d",&size);
    int i,j;
    for(i = 1;i <= size;i ++)
        for(j = 1;j <= size;j ++)
            scanf("%d",&num[i][j]);
    getsum();
    if(max <= 0){
        printf("%lld\n",max);
        return 0;
    }
    solve();
    return 0;
}