Cod sursa(job #2947449)

Utilizator iuliacarpIulia Carp iuliacarp Data 26 noiembrie 2022 08:52:31
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <deque>
using namespace std;
ifstream cin("buline.in");
ofstream cout("buline.out");
deque <int> D;
int A[400001],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>A[i]>>x;
        if(x==0) A[i]=(-1)*A[i];
        A[i+n]=A[i];
    }
    n=n*2;
    for(int i=1;i<=n;i++)
        A[i]=A[i-1]+A[i];
    int smax=0;
    for(int i=1;i<=n;i++)
    {
        while(!D.empty()&&A[i]-A[i-1]>=A[i]-A[D.back()])
            D.pop_back();
        D.push_back(i-1);
        while(!D.empty()&&D.front()<i-n/2)
            D.pop_front();
        if(smax<A[i]-A[D.front()])
            smax=A[i]-A[D.front()];
    }
    cout<<smax;
    return 0;
}