# Cod sursa(job #1777537)

Utilizator Data 12 octombrie 2016 16:51:45 Ferma2 60 cpp done Arhiva de probleme 1.21 kb
``````#include <bits/stdc++.h>

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

int n,w,s;
int a[NMax][NMax];
int dp[4][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];
dp[1][i][j] = a[i][j];
s += a[i][j];
}
}
w = n - w;
for(int k = 2; k < w; ++k){
int E = 2;
for(int i = k; i <= n; ++i){
for(int j = 1; j <= i - k + 1; ++j){
dp[E][i][j] = a[i][j] + dp[E - 1][i][j + 1] + dp[E - 1][i - 1][j] - dp[E - 2][i - 1][j + 1];
}
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
dp[E - 2][i][j] = dp[E - 1][i][j];
dp[E - 1][i][j] = dp[E][i][j];
}
}
}
int E = 2,ans = INF;
for(int i = w; i <= n; ++i){
for(int j = 1; j <= i - w + 1; ++j){
dp[E][i][j] = a[i][j] + dp[E - 1][i][j + 1] + dp[E - 1][i - 1][j] - dp[E - 2][i - 1][j + 1];
ans = min(dp[E][i][j],ans);
}
}
g << s - ans << '\n';
return 0;
}
``````