Cod sursa(job #2189934)

Utilizator theo2003Theodor Negrescu theo2003 Data 29 martie 2018 13:49:04
Problema Teren Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#include <vector>

using namespace std;

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

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

int main() {
	in>>size1>>size2>>max_;
	partsum = vector<vector<char> >(size1 + 1, vector<char>(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<char> 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++;

					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;
}