# Cod sursa(job #1784625)

Utilizator Data 20 octombrie 2016 12:01:17 Ferma2 100 cpp done Arhiva de probleme 1.17 kb
``````#include <fstream>
#include <cstdio>
#define VAL 1005
#define INF 0x3f3f3f3f

using namespace std;

int N, K, i, j;
int sum, v[VAL][VAL];
int col[VAL][VAL], mn;
int lin[VAL][VAL];
int diag[VAL][VAL];
int dp[VAL][VAL], l, c;

int main()
{
freopen("ferma2.in", "r", stdin);
freopen("ferma2.out", "w", stdout);
scanf("%d %d", &N, &K);
l=c=N-K;
K=l;
mn=INF;
for (i=1; i<=N; i++)
{
for (j=1; j<=i; j++)
{
scanf("%d", &v[i][j]);
col[i][j]=col[i-1][j]+v[i][j];
lin[i][j]=lin[i][j-1]+v[i][j];
diag[i][j]=diag[i-1][j-1]+v[i][j];
sum+=v[i][j];
if (i==l && j==c)
{
dp[i][j]=sum;
mn=dp[i][j];
}
}
}
for (i=l+1; i<=N; i++)
{
for (j=c; j<=i; j++)
{
if (j!=i)
dp[i][j]=dp[i-1][j]+(lin[i][j]-lin[i][j-K])-(diag[i-1][j]-diag[i-1-K][j-K]);
else
dp[i][j]=dp[i][j-1]-(col[i][j-K]-col[i-K][j-K])+(diag[i][j]-diag[i-K][j-K]);
mn=min(mn, dp[i][j]);
}
}
if (mn==INF)
mn=sum;
printf("%d\n", sum-mn);
return 0;
}
``````