Cod sursa(job #306060)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 19 aprilie 2009 16:44:42
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include<algorithm>
using namespace std;

#define DIM 200001
#define INF -1000001

int n,max0,a[DIM],dq[2*DIM],sum[2*DIM];

void solve(){
    int i,st,dr,tip,pozi,pozf;

    scanf("%d",&n);
    for(i=1; i<=n; ++i){
        scanf("%d%d",&a[i],&tip);
        if(!tip)
            a[i]*=-1;}
    a[0]=a[n];
    for(i=1; i<=2*n; ++i)
        sum[i]=a[i%n]+sum[i-1];
    st=1;
    dr=0;
    max0=INF;
    for(i=1; i<=2*n; ++i){
        for(; st<=dr&&sum[i]<=sum[dq[dr]]; --dr);
        dq[++dr]=i;
        if(dq[st]==i-n)
            ++st;
        if(sum[i]-sum[dq[st]]>max0){
            max0=sum[i]-sum[dq[st]];
            pozi=dq[st]+1;
            pozf=i;}}
    printf("%d %d %d",max0,pozi,pozf-pozi+1);}

int main(){

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

    solve();
    return 0;}