Cod sursa(job #2404027)

Utilizator Data 12 aprilie 2019 11:06:59 Ferma2 100 cpp-64 done Arhiva de probleme 1.42 kb
``````#include <bits/stdc++.h>
using namespace std;
ifstream in("ferma2.in");
ofstream out("ferma2.out");
int n,k,vert,oriz,diag,a[1005][1005],s[1005][1005],s_diag[1005][1005];
int main()
{int i,j,dif;
in>>n>>k;
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
in>>a[i][j];

///creez sumele partiale
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];

///creez sumele pe diagonala
for (dif=0;dif<n;dif++)
for (j=1;j<=n-dif;j++)
{
i=j+dif;
if (j==1)
s_diag[i][j]=a[i][j]+s_diag[i][j+1];
else
s_diag[i][j]=a[i][j]+s_diag[i-1][j-1]+s_diag[i][j+1]-s_diag[i-1][j];
}
for (i=1;i<=n;i++)s_diag[i][0]=s_diag[i][1];

///iterez prin toate posibilitatile
int suma=0,maxim=-1;
for (vert=0;vert<=k;vert++)
for (oriz=0;oriz<=k-vert;oriz++)
{
diag=k-(oriz+vert);
suma=0;
if (vert>0)
suma+=s[n][vert];
if (oriz>0)
suma+=s[n][n]-s[n][vert]-s[n-oriz][n]+s[n-oriz][vert];
if(diag>0)
suma+=s_diag[n-oriz][n-oriz-diag+1]-s_diag[vert+diag-1][vert]
+s[vert+diag-1][n]-s[vert+diag-1][vert];

maxim=max(maxim,suma);
}
out<<maxim<<"\n";
out.close();
in.close();
return 0;
}

``````