Cod sursa(job #1149257)

Utilizator sddddgjdZloteanu Anastasia sddddgjd Data 21 martie 2014 16:09:23
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include<stdio.h>
#include<deque>
int v[400000],s[400000];
std::deque <int> deq;
int main()
{
    FILE *fin,*fout;
    fin=fopen("buline.in","r");
    fout=fopen("buline.out","w");
    int n;
    fscanf(fin,"%d",&n);
    int i;
    for(i=0;i<n;i++)
    {
        int tip;
        fscanf(fin,"%d%d",&v[i],&tip);
        if(tip==0)
            v[i]=-v[i];
    }
    for(i=n;i<2*n;i++)
        v[i]=v[i-n];
    n=2*n;
    s[0]=v[0];
    for(i=1;i<n;i++)
        s[i]=s[i-1]+v[i];
    int smax=0,poz=0,l=0;
    for(i=0;i<n;i++)
    {
        while(!deq.empty()&&s[i]<=s[deq.back()])
            deq.pop_back();
        deq.push_back(i);
        if(deq.front()==i-n/2)
            deq.pop_front();
        if(smax<s[i]-s[deq.front()])
        {
            smax=s[i]-s[deq.front()];
            poz=deq.front()+1;
            l=i-poz+1;
        }
    }
    fprintf(fout,"%d %d %d",smax,poz+1,l);
    return 0;
}