Cod sursa(job #1397644)

Utilizator tudorv96Tudor Varan tudorv96 Data 23 martie 2015 17:35:39
Problema Ferma2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <fstream>
using namespace std;

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

const int N = 1005;

int d[N][N], n, k, sol, a[N][N], dg[N][N], cl[N][N], ln[N][N], st;

int main() {
    fin >> n >> k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= i; ++j) {
            fin >> a[i][j];
            dg[i][j] = dg[i-1][j-1] + a[i][j];
            ln[i][j] = ln[i][j-1]   + a[i][j];
            cl[i][j] = cl[i-1][j]   + a[i][j];
            st += a[i][j];
        }
    k = n - k;
    for (int i = 1; i <= k; ++i)
        for (int j = 1; j <= i; ++j)
            d[1][1] += a[i][j];
    sol = max(sol, st - d[1][1]);
    for (int i = 2; i <= n - k + 1; ++i) {
        d[i][1] = d[i - 1][1] + ln[i + k - 1][k] - dg[i + k - 2][k];
        sol = max(sol, st - d[i][1]);
        for (int j = 2; j <= i; ++j) {
            d[i][j] = d[i][j - 1] + dg[i + k - 1][j + k - 1] - dg[i - 1][j - 1]
                                  - cl[i + k - 1][j - 1]     + cl[i - 1][j - 1];
            sol = max(sol, st - d[i][j]);
        }
    }
    fout << sol;
}