# Cod sursa(job #1484009)

Utilizator Data 10 septembrie 2015 12:48:02 Ferma2 100 cpp done Arhiva de probleme 1.48 kb
``````#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1002
using namespace std;
int n, i, j, k, dp[maxN][maxN], sol, sum, sd;
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);
sum += 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;
if (i == n && j >= n - k + 1)
sd += si[n - i + 1 + j][j];
}
}
}
void solve()
{
int i, j;
dp[1][1] = sum - sd;
sol = dp[1][1];
k = n - k;
for (i = 1; i + k - 1 <= n; ++ i)
for (j = 1; j + k - 1 <= n - i + 1; ++ j)
if (i + j > 2)
{
dp[i][j] = si[i + j + k - 1][j + k - 1] - si[i + j + k - 1][j - 1];
if (i > 1)
dp[i][j] += dp[i - 1][j] - sl[i - 1][j + k - 1] + sl[i - 1][j - 1];
else
dp[i][j] += dp[i][j - 1] - sc[i][j - 1] + sc[i + k][j - 1];

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