Cod sursa(job #2336940)

Utilizator ApostolIlieDanielApostol Ilie Daniel ApostolIlieDaniel Data 5 februarie 2019 18:31:12
Problema Ferma2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000, INF = 1e9;

int l[MAXN + 1][MAXN + 1], c[MAXN + 1][MAXN + 1], d[MAXN + 1][MAXN + 1];
int a[MAXN + 1][MAXN + 1];
int main() {
  int n, k, i, j, there, remains, sol, s;
  freopen ("ferma2.in", "r", stdin);
  freopen ("ferma2.out", "w", stdout);
  scanf ("%d%d", &n, &k);
  for (i = 1; i <= n; i++)
    for (j = 1; j <= i; j++)
      scanf ("%d", &a[i][j]);
  s = 0;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      s += a[i][j];
      l[i][j] = l[i][j - 1] + a[i][j];
      c[i][j] = c[i - 1][j] + l[i][j];
      d[i][j] = d[i - 1][j - 1] + l[i][j];
    }
  there = n - k;
  sol = INF;
  for (i = there; i <= n; i++)
    for (j = there; j <= i; j++) {
      remains = d[i][j] - c[i][j - there] + c[i - there][j - there] - d[i - there][j - there];
      sol = min (sol, remains);
    }
  printf ("%d\n", s - sol);
  return 0;
}