Cod sursa(job #1085657)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 17 ianuarie 2014 10:46:11
Problema Evaluarea unei expresii Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include<iostream>
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;

ifstream fin("date.in");
ofstream fout("date.out");

int n,m,a[100][100],b[100][100],ind,jnd,maxx;

inline void Citire()
{
    int i,j;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            fin>>a[i][j];
}

inline void Formeaza()
{
    int i,j;
    for (j=1;j<=m;j++)
            for (i=1;i<=n;i++)
                {
                    b[i][j]=b[i-1][j]+a[i][j];
                 }
}

inline void Rezolva()
{
    int i1,j1,i2,j2,maxim,k,suma,poz;
    i1=1;
    while (i1<=n)
        {
            i2=i1;
            while (i2<=n)
                {
                    suma=b[i2][1]-b[i1-1][1];maxim=suma;
                    for (k=2;k<=m;k++)
                            {if (b[i2][k]-b[i1-1][k]>suma+b[i2][k]-b[i1-1][k])
                                {
                                    suma=b[i2][k]-b[i1-1][k];
                                }
                                else suma+=b[i2][k]-b[i1-1][k];
                             if (suma>maxim)
                                {
                                    maxim=suma;poz=k;
                                }
                            }
                    if (maxim>maxx)
                        {
                            maxx=maxim;
                            j2=j1=poz;
                            while (maxim!=0)
                                {
                                    maxim-=b[i2][j1]-b[i1-1][j1];
                                    j1--;
                                }
                            j1++;
                            ind=i1;jnd=i2;
                        }
                    i2++;
                }
            i1++;
        }
    fout<<ind<<j1<<" "<<jnd<<j2<<"\n";
}

int main()
{
    Citire();
    Formeaza();
    Rezolva();
    return 0;
}