Cod sursa(job #915670)

Utilizator CosminRusuCosmin Rusu CosminRusu Data 15 martie 2013 10:44:40
Problema Subsir crescator maximal Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.58 kb
/*
#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;
}