Cod sursa(job #1011368)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 16 octombrie 2013 19:38:19
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
using namespace std;
ifstream fin ("buline.in");
ofstream fout ("buline.out");
int v[400001], s[400001], d[400001],i,j,n,a,b,sum,p,u,pc,dc,pmax,dmax,maxim;

int main () {

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>a>>b;
        if (b==0)
            v[i]=v[i+n]=a * (-1);
        else
            v[i]=v[i+n]=a;
    }
    for (i=1;i<=n+n;i++){
        s[i]= s[i-1] +v[i];
    }
    p=1;
    d[++u]=0;
    for (i=1;i<=n+n;i++) {
        sum= s[i]-s[d[p]];
        pc=d[p]+1;
        dc=i-d[p];
        if ((sum>maxim)||(sum==maxim && pc< pmax) || (sum==maxim && pc==pmax && dc < dmax) ){
            maxim=sum;
            pmax=pc;
            dmax=dc;
        }
        while (p <= u && s[i] <= s[d[u]])
            u --;
        d[++u] = i;

        if (d[p]+n == i)
            p++;
    }
    fout <<maxim<<" "<<pmax<<" "<<dmax<<"\n";
    return 0;
}