Cod sursa(job #1326615)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 25 ianuarie 2015 18:57:33
Problema Subsecventa de suma maxima Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include<fstream>
using namespace std;
ifstream in("sotron.in");
ofstream out("sotron.out");
const int NMAX = 240;
const int INF = 1 << 30;

int v[NMAX + 5][NMAX + 5],a[NMAX + 5],n,sol = -INF,lg;

void read()
{
    in>>n;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= n ; j++)
            in>>v[i][j];
    in.close();

}

int sub_max()
{

    int smax = a[1],best = a[1];
    for(int i = 2 ; i <= lg ; i++){
        if(a[i] + smax > a[i])
            smax += a[i];
        else
            smax = a[i];
        best = max(best,smax);
    }
    return best;
}

void solve()
{

    for(int i = 1 ; i <= n ; i += 2 ){
        lg = 0;
        int x = i,y = 1;
        a[++lg] = v[x][y];
        while(1){
            if((x+y)%2 == 0 && x > 1){
                --x;
                a[++lg] = v[x][y];
            }
            else if((x+y)%2 == 1 && y < n){
                ++y;
                a[++lg] = v[x][y];
            }
            else
                break;
        }
        sol = max(sol,sub_max());
    }

    for(int i = 2 ; i <= n ; i += 2){
        lg = 0;
        int x = n,y = i;
        a[++lg] = v[x][y];
        while(1){
            if((x+y)%2 == 0 && x > 1){
                --x;
                a[++lg] = v[x][y];
            }
            else if((x+y)%2 == 1 && y < n){
                ++y;
                a[++lg] = v[x][y];
            }
            else
                break;
        }
        sol = max(sol,sub_max());
    }
    out<<sol;
}

int main()
{

    read();
    solve();
    return 0;
}