Cod sursa(job #201284)

Utilizator ShootMeBistriceanu Andrei ShootMe Data 30 iulie 2008 10:57:51
Problema Teren Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
        int **a;
       
        int N, M, X;

        ifstream f;
		f.open ("teren.in");
        f >> N;
        f >> M;
        f >> X;
        a = new int*[N];
        for (int i = 0 ;i < N; i++)
                a[i] = new int[M];
        for (int i = 0 ; i < N; i++)
                for ( int j = 0 ; j <  M ; j++)
                        f >> a[i][j];
		f.close();
       
        int *sum = new int[N];
		for (int i = 0 ; i < N ; i++)
			sum[i] = 0;
        int sumMax = 0;
        for (int i = 0 ; i < M ; i++)
		{
                for ( int j = i ; j < M ; j++)
                {
                        for (int k = 0 ; k < N ; k++)
                                sum[k] += a[k][j];

                        int posStart = 0;
						int posEnd = 0;
						int sumPart = sum[0];
						while (posEnd < N)
						{
							if (sumPart <= X)
							{
								if ((j-i+1)*(posEnd-posStart + 1) > sumMax)
									sumMax = (j-i+1)*(posEnd-posStart + 1);

								posEnd++;
								sumPart += sum[posEnd];
							} else
							{
								posStart++;
								sumPart -= sum[posStart];
							}
							if ((j-i+1)*(posEnd-posStart + 1) < sumMax)
								break;
						}
                       
                               
                }
				for (int i = 0 ; i < N ; i++)
					sum[i] = 0;
		}
        //output
        ofstream out;
		out.open ("teren.out");
		out << sumMax;
        out.close();
        return 0;

}