Cod sursa(job #1751185)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 31 august 2016 21:41:30
Problema Balans Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <iostream>
#include <cstdio>
#include <iomanip>
#define MAXN 164
#define MAXM 164

using namespace std;

int a[2*MAXN][2*MAXM];
int pre[2*MAXN][2*MAXN], deck[2*MAXM];
double crt[2*MAXM];
int n, m, r, c;

void citire()
{
	scanf("%d %d %d %d", &n, &m, &r, &c);
    for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			scanf("%d", &a[i][j]);
			a[i][j+m] = a[i+n][j] = a[i+n][j+m] = a[i][j];
		}
	for (int i = 1; i <= 2*n; i++)
		for (int j = 1; j <= 2*m; j++)
			pre[i][j] = pre[i-1][j] + a[i][j];

}
bool check(int i1, int i2, double x) {
    for(int i=1; i<=m; ++i) crt[i]=pre[i2][i]-pre[i1-1][i]-x*(i2-i1+1)+crt[i-1];
    if(crt[c]>=0) return 1;
    int st=0,dr=-1;
    for(int i=c+1; i<=m; ++i) {
        for(;st<=dr && crt[deck[dr]]>=crt[i-c]; --dr);
        deck[++dr]=i-c;
        for(;st<dr && i-deck[st]+1>m; ++st);
        if(crt[i]-crt[deck[st]]>=0) return 1;
    }
    return 0;
}
//int check(int stx, int len, double k)
//{
//    for (int i = 1; i <= m; i++)
//        crt[i] = crt[i-1] + pre[stx+len-1][i] - pre[stx-1][i] - (k*len);
//    if (crt[c] >= 0) return 1;
//    int st = 0, dr = -1;
//    for (int i = c+1; i <= m; i++) {
//        while (st <= dr && crt[i-c] <= crt[deck[dr]])
//			dr--;
//		deck[++dr] = i-c;
//        while (st < dr && i-deck[st]+1 > m)
//			st++;
//        double scad = crt[deck[st]];
//        if (crt[i]-scad >= 0) return 1;
//    }
//    return 0;
//}

void solve()
{
    int rez = 0;
     for(int i1=1; i1<=n; ++i1) for(int i2=i1+r-1; (i2-i1+1)<=n && i2<=2*n; ++i2) {
        int ls=rez,ld=(1<<30),m;
        if(!check(i1,i2,ls/1000.0)) continue;
        for(int i=1; i<=30 && ls<ld; ++i) {
            m=(ls+ld)/2;
            if(check(i1,i2,m/1000.0)) ls=m;
            else ld=m-1;
        }
        for(;check(i1,i2,ls/1000.0);++ls);
        if(!check(i1,i2,ls/1000.0)) --ls;
        rez=max(rez,ls);
    }
	cout <<fixed<<setprecision(3)<<rez/1000.0;
}

int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);

    citire();
    solve();

	return 0;
}