Cod sursa(job #1590607)

Utilizator LucianTLucian Trepteanu LucianT Data 5 februarie 2016 13:01:13
Problema Balans Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#define maxN 302
using namespace std;
long long n, m, c, r, a[maxN][maxN], i, j, k;
long long sol, sum[maxN], aux;
long long ii, jj;
long long st, dr;
deque<int> q;
bool verif(long long x)
{
    long long i, j, k;
    for(i = 1; i <= n; i++)
    {
        memset(sum, 0, sizeof(sum));
        //sume partiale
        for(j = i; j < min(2*n, i+r-1); j++)
        {
            aux=0;
            for(k = 1; k <= 2 * m; k++)
                aux += 1LL*a[j][k] - x, sum[k] += aux;
        }
        for(j = i+r-1; j <= min(2*n, i+n-1); j++)
        {
            aux=0;
            for(k = 1; k <= 2*m; k++)
                aux += 1LL*a[j][k]-x, sum[k] += aux;
            //min_deque
            q.clear();
            for(k = c; k <= 2*m; k++)
            {
                while(!q.empty() && sum[k-c] <= sum[q.front()])
                    q.pop_front();
                while(!q.empty() && k-q.back() > m)
                    q.pop_back();
                q.push_front(k-c);
                if(sum[k] >= sum[q.back()]) return true;
            }
        }
    }
    return false;
}
void cb(long long st, long long dr)
{
    long long mij;
    while(st <= dr)
    {
        mij = st+(dr-st)/2;
        if(verif(mij)) sol=mij, st = mij+1;
        else dr = mij-1;
    }
}
int main()
{
    freopen("balans.in", "r", stdin);
    freopen("balans.out", "w", stdout);
    scanf("%lld %lld %lld %lld", &n, &m, &r, &c);
    for(i = 1; i <= n; i++)
        for(j = 1; j <= m; j++)
        scanf("%lld", &a[i][j]), a[i][j] *= 1000;
    //circularitate
    for(i = 1; i <= 2*n; i++)
        for(j = 1; j <= 2*m; j++)
            if(!(i <= n && j <= m))
            {
                ii = (i-1)%n+1;
                jj = (j-1)%m+1;
                a[i][j] = a[ii][jj];
            }
    //caut binar solutia
    st=0, dr=(1LL<<32);
    cb(st, dr);
    printf("%lld.%lld", sol/1000, sol%1000);
    return 0;
}