Pagini recente » Cod sursa (job #174558) | Cod sursa (job #1771396) | Cod sursa (job #1623728) | Cod sursa (job #1050698) | Cod sursa (job #1528207)
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
#include <deque>
#include <limits>
using namespace std;
template <typename Cmp>
class my_deque{
Cmp cmp;
deque<int> buf;
public:
my_deque(Cmp c): cmp(c){}
void push(const int x){
while(!buf.empty() && !cmp(buf.back(), x)){
buf.pop_back(); }
buf.push_back(x); }
void pop(const int x){
if(!buf.empty() && buf.front() == x){
buf.pop_front(); } }
int front(){
return buf.front(); } };
bool exista_subsecv_poz(const vector<long long>& s_part, const int min_len, const int max_len){
const int n = s_part.size();
auto sort_by_s_part = [&s_part](const int a, const int b){
return s_part[a] < s_part[b]; };
my_deque<decltype(sort_by_s_part)> dq(sort_by_s_part);
for(int i = 0; i < n; ++i){
dq.pop(i-max_len-1);
if(i-min_len >= 0){
dq.push(i-min_len);
if(s_part[i] >= s_part[dq.front()]){
return true; } } }
return false; }
bool exista_submat_poz(const vector<vector<int> >& v, const int min_r, const int max_r, const int min_c, const int max_c, const long long delta){
const int r = v.size(), c = v[0].size();
vector<long long> s_part_col(c+1, 0);
for(int i = 0; i+min_r <= r; ++i){
fill(begin(s_part_col), end(s_part_col), 0);
for(int j = i; j < r && j-i <= max_r; ++j){
long long la_stanga = 0;
for(int k = 1; k <= c; ++k){
la_stanga += v[j][k-1];
la_stanga -= delta;
s_part_col[k] += la_stanga; }
if(j-i+1 >= min_r && exista_subsecv_poz(s_part_col, min_c, max_c)){
return true; } } }
return false; }
int cbin(vector<vector<int> >& v, const int min_r, const int max_r, const int min_c, const int max_c){
long long st = 0, dr = 1000010000;
for(int step = 1ll<<(int)log2(dr-st+1); step > 0; step /= 2){
if(st+step <= dr){
if(exista_submat_poz(v, min_r, max_r, min_c, max_c, st+step)){
st += step; } } }
return st; }
int main(){
ifstream f("balans.in");
ofstream g("balans.out");
int n, m, r, c;
f >> n >> m >> r >> c;
if(r == 0){
r = 1; }
if(c == 0){
c = 1; }
vector<vector<int> > v(2*n, vector<int>(2*m, 0));
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
f >> v[i][j];
v[i][j] *= 1000;
v[i+n][j] = v[i][j+m] = v[i+n][j+m] = v[i][j]; } }
const int rez = cbin(v, r, n, c, m);
g << fixed << setprecision(3) << rez/1000 << '.' << setw(3) << setfill('0') << rez%1000 << '\n';
return 0; }