Cod sursa(job #2190414)

Utilizator theo2003Theodor Negrescu theo2003 Data 30 martie 2018 18:23:15
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream in("teren.in");
ofstream out("teren.out");

vector<vector<int> > partsum;
int size1, size2, max_;
int maxarea;

int main() {
    in>>size1>>size2>>max_;
    partsum = vector<vector<int> >(size1 + 1, vector<int>(size2, 0));

    for(int x = 1, tmp; x<=size1; x++) {
        for(int y = 0; y<size2; y++) {
            in>>tmp;
            partsum[x][y] = partsum[x-1][y] + tmp;
        }
    }

    /*for(vector<int> tmp : partsum) {
        for(int x : tmp)
            out<<x<<' ';

        out<<'\n';
    }*/

    for(int line1 = 1; line1<=size1; line1++) {
        for(int line2 = line1; line2<=size1; line2++) {
            for(int st = 0, dr = 0, sum = 0; dr<size2; dr++) {
                sum+=partsum[line2][dr] - partsum[line1 - 1][dr];

                while(sum>max_ && st <= dr) {
                    sum -= partsum[line2][st] - partsum[line1 - 1][st];
                    st++;
/*
                    if(st>dr) {
                        dr = st;
                        sum = partsum[line2][dr] - partsum[line1 - 1][dr];
                    }
                    else
                        sum-=partsum[line2][st] - partsum[line1 - 1][st];
*/
                }

                maxarea = max(maxarea, (dr-st+1)*(line2-line1+1));
            }
        }
    }

    out<<maxarea;
}