Cod sursa(job #2361169)

Utilizator Iulia25Hosu Iulia Iulia25 Data 2 martie 2019 13:33:07
Problema Ferma2 Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>

using namespace std;

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

int a[1005][1005], col[1005], lin[1005], ipo[1005];
int sp[1005][1005], sp1[1005][1005], sp2[1005][1005];
int d, Max, n, k, x;

int main()  {
  fin >> n >> k;
  for (int i = 1; i <= n; ++i)  {
    for (int j = 1; j <= i; ++j)  {
      fin >> a[i][j];
      col[j] += a[i][j];
      lin[n - i + 1] += a[i][j];
      ipo[i - j + 1] += a[i][j];
    }
  }
  for (int i = 1; i <= n; ++i)  {
    for (int j = 1; j <= n; ++j)
      sp[i][j] = sp[i - 1][j] + sp[i][j - 1] - sp[i - 1][j - 1] + a[i][j];
  }
  for (int i = n; i; --i)  {
    for (int j = 1; j <= n; ++j)
      sp1[i][j] = sp1[i + 1][j] + sp1[i][j - 1] - sp1[i + 1][j - 1] + a[i][j];
    for (int j = n; j; --j)
      sp2[i][j] = sp2[i + 1][j] + sp2[i][j + 1] - sp2[i + 1][j + 1] + a[i][j];
  }
  for (int i = 2; i <= n; ++i)  {
    col[i] += col[i - 1];
    lin[i] += lin[i - 1];
    ipo[i] += ipo[i - 1];
  }
  for (int i = 0; i <= k; ++i)  {
    for (int j = 0; i + j <= k; ++j)  {
      d = k - i - j;
      x = col[i] + lin[j] + ipo[d] - sp[d][i] - sp1[n - j + 1][i] - sp2[n - j + 1][d];
      if (x > Max)  {
        Max = x;
//        fout << x << ' ' << i << ' ' << j << ' ' << d << '\n';
      }
    }
  }
  fout << Max;
  return 0;
}