Cod sursa(job #2201391)

Utilizator Anakin1001George Giorgiu Gica Anakin1001 Data 4 mai 2018 17:02:24
Problema Buline Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int i,l,p,p1,u,dq[400001],v[400001],a,n,maxi;
int main()
{   f>>n;
    for(i=1;i<=n;i++){
        f>>v[i]>>a;
        if(a==0)
            v[i]=-v[i];
        v[i+n]=v[i];
        v[i]=v[i-1]+v[i];
    }
    for(i=n+1;i<=2*n;i++)
        v[i]=v[i-1]+v[i];
    p=0;u=0;
    for(i=1;i<=2*n;i++){
        while(p<=u&&v[i]<=v[dq[u]])
            u--;
        dq[++u]=i;
        if(i-dq[p]>=n)
            p++;
        if(i-dq[p]<n){
            if(maxi<v[i]-v[dq[p]]){
                maxi=v[i]-v[dq[p]];
                l=i-dq[p];
                p1=dq[p+1];
            }
        }
    }
    g<<maxi<<' '<<p1<<' '<<l;
    return 0;
}