# Cod sursa(job #1953237)

Utilizator Data 4 aprilie 2017 18:36:36 Ferma2 100 cpp done Arhiva de probleme 1.98 kb
``````#include <bits/stdc++.h>

using namespace std;
ifstream f("ferma2.in");
ofstream g("ferma2.out");

const int NMax = 1003;

int n,k;
int a[NMax][NMax],c[NMax][NMax],l[NMax][NMax],d[NMax][NMax],d2[NMax][NMax];

int trian(int i,int j,int lat){
int s = 0;
s += c[n][j - 1];

s += l[i + lat][j];

s += d[i + lat - 1][j + lat];

if(i - 2 >= 1)
s -= d2[i - 2][j - 1];

return s;
}
int main()
{
f >> n >> k;
int lat = n - k;
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= i; ++j){
f >> a[i][j];

if(i == j)
c[i][j] = c[i][j - 1] + a[i][j];
else
c[i][j] = c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1] + a[i][j];
}
}

for(int i = n; i >= 1; --i){
for(int j = i; j >= 1; --j){
if(i == j)
l[i][j] = l[i + 1][j] + a[i][j];
else
l[i][j] = l[i + 1][j] + l[i][j + 1] - l[i + 1][j + 1] + a[i][j];
}
}
for(int i = 1; i <= n; ++i){
for(int j = i; j >= 1; --j){
if(i == j)
d[i][j] = d[i - 1][j - 1] + a[i][j];
else{

if(j == 1){
d[i][j] = d[i][j + 1] + a[i][j];
}else
d[i][j] = d[i][j + 1] + d[i - 1][j - 1] - d[i - 1][j] + a[i][j];
}
}
}
for(int i = 1; i <= n; ++i){
int start = i;
for(int j = 1; j <= n - i + 1; ++j){

if(j == 1){
d2[start][j] = d2[start - 1][j] + a[start][j];
}else{
d2[start][j] = d2[start - 1][j - 1] + d2[start - 1][j] - d2[start - 2][j - 1] + a[start][j];
}
start++;
}
}
int ans = 0;
for(int i = 1; i <= n - lat + 1; ++i){
for(int j = 1; j <= i; ++j){
ans = max(ans,trian(i,j,lat));
}
}

g << ans << '\n';
return 0;
}
``````