Pagini recente » Cod sursa (job #2118012) | Cod sursa (job #1841902) | Cod sursa (job #1388810) | Cod sursa (job #1222962) | Cod sursa (job #915684)
Cod sursa(job #915684)
/*
#include <fstream>
#include <math.h>
//#define degandacire
using namespace std;
ifstream cin("joctv.in");
ofstream cout("joctv.out");
int n,sum[105][105], a[105][105], i, j, maxi=-((1<<31)-1);
int main()
{
cin>>n;
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
cin>>a[i][j];
sum[i][j]=a[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
}
#ifdef degandacire
for(i=1;i<=n;++i)
{for(j=1;j<=n;++j)
cout<<sum[i][j]<<" ";
cout<<"\n";}
#endif
for(int i1=1;i1<=n;++i1)
for(int j1=1;j1<=n;++j1)
for(int i2=i1;i2<=n;++i2)
for(int j2=j1;j2<=n;++j2)
maxi=max(maxi, (sum[i2][j2] - sum[i1-1][j2] - sum[i2][j1-1] + sum[i1-1][j1-1]));
cout<<maxi<<"\n";
cin.close();
cout.close();
return 0;
} */
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100
int a[MAX][MAX];
int stanga[MAX];
int sus[MAX][MAX],suso[MAX][MAX];
int n;
int max_val(int linie,int coloana)
{
int i,j,s,max;
max = -32000;
if(coloana == 0)
{
s = 0;
for(i=linie;i>=0;i--)
{
s = s + a[i][coloana];
stanga[i] = s;
if(max < s)
max = s;
}
}
else
{
s = 0;
for(i=linie;i>=0;i--)
{
s = s + a[i][coloana];
//if(st[i] + s > st[i])
stanga[i] = stanga[i] + s;
if(stanga[i] < s)
stanga[i] = s;
if(max < stanga[i])
max = stanga[i];
}
}
if(linie == 0)
{
s = 0;
for(j=coloana;j>=0;j--)
{
s += a[linie][j];
sus[coloana][j] = s;
if(max < s)
max = s;
}
}
else
{
s = 0;
for(j=coloana;j>=0;j--)
{
s += a[linie][j];
sus[coloana][j] = suso[coloana][j] + s;
if(sus[coloana][j] < s)
sus[coloana][j] = s;
if(max < sus[coloana][j])
max = sus[coloana][j];
}
}
return max;
}
void read_data()
{
int i,j;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
}
int** aloc(int n)
{
int i;
int** tab;
tab = (int**)malloc(n * sizeof(int*));
for(i=0;i<n;i++)
tab[i] = (int*)malloc(n * sizeof(int));
return tab;
}
void run()
{
int i,j,max;
int** sum;
sum = aloc(n);
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
max = max_val(i,j);
if(i > 0 && max < sum[i-1][j])
max = sum[i-1][j];
if(j > 0 && max < sum[i][j-1])
max = sum[i][j-1];
sum[i][j] = max;
}
memcpy(suso,sus,sizeof(sus));
}
printf("%d \n",sum[n-1][n-1]);
}
int main()
{
read_data();
run();
return 0;
}