Cod sursa(job #2083603)

Utilizator MoldooooooooMoldoveanu Stefan Moldoooooooo Data 7 decembrie 2017 21:27:01
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <climits>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int main()
{
    deque<int> D;
    int N, i, a, b, S, P, L;
    f>>N;
    int V[400010];
    for(i=1; i<=N; i++){f>>a>>b;
                        if(b==1){V[i]=a;
                                 V[i+N]=a;}
                            else{V[i]=-a;
                                 V[i+N]=-a;}
                       }
    for(i=2; i<=2*N; i++)V[i]=V[i-1]+V[i];
    S=INT_MIN;
    for(i=1; i<=2*N; i++)
    {
        while(D.size()>0 && V[D.back()]>V[i])D.pop_back();
        D.push_back(i);
        if(D.front()==i-N)D.pop_front();
        if((V[i]-V[D.front()])>S)
        {
            S=V[i]-V[D.front()];
            P=D.front()+1;
            L=i-P+1;
        }
    }
    g<<S<<" "<<P<<" "<<L;
    return 0;
}