Cod sursa(job #2593818)

Utilizator rares404AlShaytan - Balasescu Rares rares404 Data 4 aprilie 2020 17:46:05
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.65 kb
//
//  main.cpp
//  teren
//
//  Created by Eusebiu Rares on 04/04/2020.
//  Copyright © 2020 Eusebiu Rares. All rights reserved.
//

#include <iostream>
#include "fstream"

std::fstream in ("teren.in", std::ios::in) ;
std::fstream out ("teren.out", std::ios::out) ;

const int MV = 300 ;
const int INF = 2e9 ;

int psm[MV + 1][MV + 1] ;

template <typename T>
T MAX(T a, T b, T c = -INF, T d = -INF) {
	return std::max(std::max(a, b), std::max(c, d)) ;
}

template <typename T>
T MIN(T a, T b, T c = INF, T d = INF) {
	return std::min(std::min(a, b), std::min(c, d)) ;
}

template <typename T>
T MAX_M(T &a, T b) {
	if (a < b) {
		a = b ;
	}
	return a ;
}

template <typename T>
T MIN_M(T &a, T b) {
	if (a > b) {
		a = b ;
	}
	return a ;
}

int n, m, maxBad ;
int areaAnswer ;

int sumPsm(int x1, int y1, int x2, int y2) {
	return psm[x2][y2] - psm[x1 - 1][y2] - psm[x2][y1 - 1] + psm[x1 - 1][y1 - 1] ;
}

int maxArea(int left, int right) {
	int st, dr(areaAnswer / (right - left + 1)) ;
	int ret(0) ;
	for (st = 1 ; st <= n ; ++ st) {
		for ( ; dr <= n && sumPsm(st, left, dr, right) <= maxBad ; ++ dr) ;
		dr -- ;
		MAX_M(ret, (right - left + 1) * (dr - st + 1)) ;
	}
	return ret ;
}

int main(int argc, const char * argv[]) {
	in >> n >> m >> maxBad ;
	for (int i = 1 ; i <= n ; ++ i) {
		for (int j = 1 ; j <= m ; ++ j) {
			in >> psm[i][j] ;
			psm[i][j] += psm[i - 1][j] + psm[i][j - 1] - psm[i - 1][j - 1] ;
		}
	}
	for (int leftCol = 1 ; leftCol <= m ; ++ leftCol) {
		for (int rightCol = MAX(areaAnswer / n + leftCol - 1, leftCol) ; rightCol <= m ; ++ rightCol) {
			int candidate = maxArea(leftCol, rightCol) ;
			MAX_M(areaAnswer, candidate) ;
		}
	}
	out << areaAnswer ;
}