Pagini recente » Cod sursa (job #1539943) | Cod sursa (job #3333556) | Cod sursa (job #1900472) | Cod sursa (job #339440) | Cod sursa (job #3329626)
#include <bits/stdc++.h>
using namespace std;
#define USE_STD_IO 0
//#define if(USE_STD_IO) cout
#if USE_STD_IO
#define fin cin
#define fout cout
#else
ifstream fin("balans.in");
ofstream fout("balans.out");
#endif // USE_STD_IO
int n, m, r, c, i, ii, j, a[152][152], rasp;
double vv[2 * 152];
deque<int> q;
static inline bool Verif(double rap) {
for(int j = 1; j <= 2 * m; j++) {
vv[j] = vv[j - 1] + (a[ii][j] - a[i - 1][j]) - (ii - i + 1) * rap;
}
if(vv[c] >= 0) return true;
q.clear();
for(int j = c + 1; j <= 2 * m; j++) {
while(!q.empty() && vv[j - c] <= vv[q.back()]) q.pop_back();
q.push_back(j - c);
while(!q.empty() && j - q.front() + 1 > m) q.pop_front();
if(vv[j] >= vv[q.front()]) return true;
}
return false;
}
int main() {
if(USE_STD_IO) ios_base::sync_with_stdio(false);
fin.tie(nullptr);
fout.tie(nullptr);
fin >> n >> m >> r >> c;
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
fin >> a[i][j];
a[i + n][j ] = a[i][j];
a[i ][j + m] = a[i][j];
a[i + n][j + m] = a[i][j];
}
}
for(i = 1; i <= 2 * n; i++) {
for(j = 1; j <= 2 * m; j++) {
a[i][j] += a[i - 1][j];
}
}
for(i = 1; i <= n; i++) {
for(ii = i + r - 1; ii <= i + n - 1; ii++) {
int st = rasp, dr = 2e9;
int sel = st;
if(!Verif(st / 1000.0)) continue;
int pas = 30;
while(st <= dr && pas > 0) {
int mij = st + (dr - st) / 2;
if(Verif(mij / 1000.0)) {
sel = mij;
st = mij + 1;
}
else dr = mij - 1;
pas--;
}
while(Verif(sel / 1000.0)) sel++;
if(!Verif(sel / 1000.0)) sel--;
rasp = max(rasp, sel);
}
}
fout << setprecision(3) << fixed;
fout << rasp / 1000.0;
return 0;
}