Cod sursa(job #3265493)

Utilizator dgrigaGriga Darius dgriga Data 30 decembrie 2024 15:24:52
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>
#include <deque>
#define INF 2e9
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
deque<int> DQ;
int sp[400005], n;
int main()
{
    f >> n;
    for(int i=1; i<=n; i++)
    {
        int x, semn;
        f >> x >> semn;
        if(semn==0)
            x=0-x;
        sp[i]=x;
        sp[n+i]=x;
    }
    DQ.push_back(1);
    int maxi=-INF, st=0, l;
    for(int i=2; i<=n*2; i++)
    {
        sp[i]+=sp[i-1];
        while(!DQ.empty()&&i-DQ.front()>n)
        {
            DQ.pop_front();
        }
        if(sp[i]-sp[DQ.front()]>maxi)
        {
            maxi=sp[i]-sp[DQ.front()];
            st=DQ.front()+1;
            l=i-DQ.front();
        }
        while(!DQ.empty()&&sp[DQ.back()]>sp[i])
        {
            DQ.pop_back();
        }
        DQ.push_back(i);
    }
    g << maxi << " " << st << " " << l;
    return 0;
}