# Cod sursa(job #779921)

Utilizator Data 19 august 2012 01:39:21 Ferma2 20 cpp done Arhiva de probleme 1.07 kb
``````#include <fstream>

using namespace std;

ifstream fin("ferma2.in");
ofstream fout("ferma2.out");

int N , K , dp[2][1005][1005] , s[3][1005][1005];

int main()
{
int ans = 0 , L = 0 , val;
fin>>N>>K;
for(int i = 1;i <= N;++i) {
for(int j = 1;j <= i;++j){
fin>>val;
s[0][i][j] = s[0][i][j - 1] + val;
s[1][i][j] = s[1][i - 1][j] + val;
s[2][i][j] = s[2][i - 1][j - 1] + val;
}
}
for(int k = 1;k <= K;++k,L = 1 - L) {
for(int i = 0;i <= N && i <= K;i++) {
for(int j = 0;j <= N && i + j <= K;j++) {
int lastDim = N - k + 1;
int x = i + 1;
int y = j + 1;
dp[1 - L][x][y] = 0;
dp[1 - L][x][y] = max(dp[1 - L][x][y], dp[L][x - 1][y] + s[2][x - 1 + lastDim - 1][y + lastDim - 1] - s[2][x - 2][y - 1]);
dp[1 - L][x][y] = max(dp[1 - L][x][y], dp[L][x][y - 1] + s[1][x + lastDim - 1][y - 1] - s[1][x  - 1][y - 1]);
dp[1 - L][x][y] = max(dp[1 - L][x][y], dp[L][x][y] + s[0][x + lastDim - 1][y + lastDim - 1] - s[0][x + lastDim - 1][y - 1]);
ans = max(ans,dp[1 - L][x][y]);
}
}
}
fout<<ans;
return 0;
}

``````