# Cod sursa(job #1851264)

Utilizator Data 19 ianuarie 2017 16:14:21 Ferma2 100 cpp done Arhiva de probleme 1.78 kb
``````#include <bits/stdc++.h>

#define pb push_back
#define f first
#define s second
#define pii pair<int, int>
#define mp make_pair

using namespace std;

const string name = "ferma2",
in_file = name + ".in",
out_file = name + ".out";

ifstream fin(in_file);
ofstream fout(out_file);

const int MAX = 1e3 + 5;

int n, k;
int triangle[MAX][MAX];
int sum_line[MAX][MAX], sum_diag[MAX][MAX];
int dp[MAX][MAX];
int sum_total;

int compute_first(int x, int y, int length) {
int sum = 0;
for (int i = 0; i < length; i++) {
for (int j = 0; j < length - i; j++) {
sum += triangle[x - i][y + j];
}
}
return sum;
}

int main() {
fin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
fin >> triangle[i][j];
sum_total += triangle[i][j];
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
sum_line[i][j] = triangle[i][j] + sum_line[i][j - 1];
}
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n - i + 1; j++) {
sum_diag[i][j] = triangle[i + j - 1][j] + sum_diag[i][j - 1];
}
}

int length_triangle = n - k;
if (!length_triangle) {
fout << sum_total;
return 0;
}

for (int j = 1; j <= n; j++) {
int current_line = length_triangle + j - 1;
if (current_line < 0 || current_line > n) {
break;
}

dp[current_line][j] = compute_first(current_line, j, length_triangle);
for (int i = current_line + 1; i <= n; i++) {
dp[i][j] = dp[i - 1][j] +
sum_line[i][j + length_triangle - 1] - sum_line[i][j - 1] -
sum_diag[i - current_line][j + length_triangle - 1] + sum_diag[i - current_line][j - 1];
}
}

int minn = sum_total;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i][j]) {
minn = min(minn, dp[i][j]);
}
}
}

fout << sum_total - minn;

return 0;
}``````