Cod sursa(job #1484006)

Utilizator Data 10 septembrie 2015 12:42:49 Ferma2 80 cpp done Arhiva de probleme 1.41 kb
``````#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1002
using namespace std;
int n, i, j, k, dp[maxN][maxN], sol;
int sl[maxN][maxN], sc[maxN][maxN], si[2 * maxN][maxN];
{
int x;
freopen("ferma2.in", "r", stdin);
scanf("%d %d", &n, &k);
for (i = 1; i <= n; ++ i)
{
for (j = 1; j <= i; ++ j)
{
scanf("%d", &x);
sl[n - i + 1][j] = sl[n - i + 1][j - 1] + x;
sc[n - i + 1][j] = sc[n - i + 2][j] + x;
si[n - i + 1 + j][j] = si[n - i + 1 + j][j - 1] + x;
}
}
}
void solve()
{
int l, i, j;
for (l = n - k + 1; l <= n; ++ l)
{
for (i = 1; i + l - 1 <= n; ++ i)
for (j = 1; j + l - 1 <= n - i + 1; ++ j)
{
dp[i][j] = dp[i][j] + si[i + j + l - 1][j + l - 1] - si[i + j + l - 1][j - 1];

if (dp[i][j] < dp[i + 1][j] + sl[i][j + l - 1] - sl[i][j - 1])
dp[i][j] = dp[i + 1][j] + sl[i][j + l - 1] - sl[i][j - 1];

if (dp[i][j] < dp[i][j + 1] + sc[i][j] - sc[i + l][j])
dp[i][j] = dp[i][j + 1] + sc[i][j] - sc[i + l][j];

if (l == n && dp[i][j] > sol)
sol = dp[i][j];
}
}
}
void write()
{
freopen("ferma2.out", "w", stdout);
printf("%d\n", sol);
}
int main()
{