Pagini recente » Cod sursa (job #274618) | Cod sursa (job #2157767) | Cod sursa (job #1048870) | Cod sursa (job #2799314) | Cod sursa (job #2593809)
//
// 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 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(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] ;
}
}
int areaAnswer(0) ;
for (int leftCol = 1 ; leftCol <= m ; ++ leftCol) {
for (int rightCol = leftCol ; rightCol <= m ; ++ rightCol) {
int candidate = maxArea(leftCol, rightCol) ;
MAX_M(areaAnswer, candidate) ;
}
}
out << areaAnswer ;
}