Cod sursa(job #1241115)

Utilizator apopeid15Apopei Daniel apopeid15 Data 12 octombrie 2014 17:57:56
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <cstdio>
#include <deque>
#define MAX 496969
using namespace std;
int v[MAX],sp[MAX];
deque <int> dubla;
int main()
{
    int n,smax=MAX-2*MAX,poz,lung;
    freopen("buline.in","r",stdin);
    freopen("buline.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        int cul;
        scanf("%d%d",&v[i],&cul);
        v[i]=v[i+n]=((!cul)?-(v[i]):v[i]);
        sp[i]=sp[i-1]+v[i];
    }
    int stop=2*n;
    for(int i=n+1;i<=stop;++i)sp[i]=sp[i-1]+v[i];
    for(int i=1;i<=stop;++i){
        while(!dubla.empty() and sp[i]<=sp[dubla.back()])dubla.pop_back();
        dubla.push_back(i);
        if(dubla.front()==i-n)dubla.pop_front();
        if(smax<sp[i]-sp[dubla.front()]){
            smax=sp[i]-sp[dubla.front()];
            poz=dubla.front()+1;
            lung=i-poz+1;
        }
    }
    printf("%d %d %d\n",smax,poz,lung);
    return 0;
}