Cod sursa(job #1633909)

Utilizator adiXMGemene Adrian adiXM Data 6 martie 2016 12:59:30
Problema Buline Scor 100
Compilator cpp Status done
Runda preoji_5 Marime 0.89 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
const int NMAX=200005;
int v[NMAX+NMAX],s[NMAX+NMAX];
deque <int> D;
int main()
{
    int n,x,y;
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>x>>y;
        if(y==0)
            v[i]=v[i+n]=-x;
        else
            v[i]=v[i+n]=x;
    }
    for(int i=1;i<=2*n;i++)
        s[i]=s[i-1]+v[i];
    int sol=0,st=0,lng=0;
    D.push_back(1);
    for(int i=2;i<=2*n;i++)
    {
        while(i-n>D.front())
        {
            D.pop_front();
        }
        if(s[i]-s[D.front()] > sol)
        {
            sol=s[i]-s[D.front()];
            st=D.front()+1;
            lng=i-D.front();
        }
        while(!D.empty() && s[i]<s[D.back()])
            D.pop_back();
        D.push_back(i);
    }
    g<<sol<<" "<<st<<" "<<lng<<"\n";
    return 0;
}