Cod sursa(job #1779648)

Utilizator Data 15 octombrie 2016 15:24:32 Ferma2 80 cpp done Arhiva de probleme 1.4 kb
``````#include <bits/stdc++.h>

#define NMax 1005
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("ferma2.in");
ofstream g("ferma2.out");

int n,w,s,ans;
int a[NMax][NMax];
int up[NMax][NMax],down[NMax][NMax],diag[NMax][NMax];

int main()
{
f >> n >> w;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
f >> a[i][j];
s += a[i][j];

if(i == j)
up[i][j] = up[i][j - 1] + a[i][j];
else
up[i][j] = up[i - 1][j] + up[i][j - 1] - up[i - 1][j - 1] + a[i][j];

diag[i][j] = diag[i - 1][j - 1] + a[i][j] + diag[i - 1][j] - diag[i - 2][j - 1];
}
}
for(int i = n; i >= 1; --i){
for(int j = 1; j <= i; ++j){
down[i][j] = down[i + 1][j] + down[i][j - 1] - down[i + 1][j - 1] + a[i][j];
}
}
int dim = n - w;
for(int i = 1; i <= n - dim + 1; ++i){
for(int j = 1; j <= i; ++j){
ans = max(ans,up[i + dim - 1][j - 1]  + down[i + dim][j + dim - 1] + (s - up[n][j + dim - 1])
+ diag[i + dim - 2][j + dim - 1] - diag[i - 2][j - 1]);
/*  g << s - (up[i + dim - 1][j - 1]  + down[i + dim][j + dim - 1] + (s - up[n][j + dim - 1])
+ diag[i + dim - 2][j + dim - 1] - diag[i - 2][j - 1]) << ' '; */
}
//  g << '\n';
}
g << ans << '\n';
return 0;
}
``````