Cod sursa(job #850712)

Utilizator Athena99Anghel Anca Athena99 Data 8 ianuarie 2013 20:41:57
Problema Balans Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cassert>
#include <cstdio>
#include <algorithm>

const int dim=155;
using namespace std;
int d[dim],v[dim],deque[dim];

int deq(int q,int k)
{
    int max=-1,start=1,stop=0,i=0;

    for (i=1; i<=q; ++i)
    {
        while (start<=stop && v[i]>=v[deque[stop]])
            --stop;

        deque[++stop]=i;

        if (deque[start]==i-k)
            ++start;

        if (k<=i && v[deque[start]]>max)
            max=v[deque[start]];
    }

    return max;
}

int main()
{
    int n=0,m=0,l=0,c=0,i=0,j=0;
    float sum=0;

    assert(freopen("balans.in","r",stdin));
    assert(freopen("balans.out","w",stdout));

    assert(scanf("%d%d%d%d",&n,&m,&l,&c));

    for (i=1; i<=n; ++i)
    {
        for (j=1; j<=m; ++j)
            assert(scanf("%d",&v[j]));
        for (j=m+1; j<2*m; ++j)
            v[j]=v[j%m];
        v[2*m]=v[m];

        d[i]=deq(m,c);
    }

    sort(d+1,d+n+1);

    for (i=n; i>n-l; --i)
        sum+=d[i];
    sum=sum/(l*c);

    assert(printf("%.3lf",sum));

    return 0;
}