Cod sursa(job #2009899)

Utilizator rexlcdTenea Mihai rexlcd Data 11 august 2017 09:01:55
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

int v[400002],dp[400002];
deque < pair < int , int > > q;

int main()
{
    ifstream f("buline.in");
    ofstream g("buline.out");
    int n,vmax=-0x3f3f3f3f,st,l;
    f>>n;
    for(int i=1,j=n+1;i<=n;i++,j++)
    {
        int x,y; f>>x>>y;
        v[i]=(y?x:-x);
        v[j]=v[i];
    }
    for(int i=1;i<=n*2;i++)
        dp[i]=dp[i-1]+v[i];
    q.push_back(make_pair(0,0));
    for(int i=1;i<=n*2;i++)
    {
        while(!q.empty() && dp[i]<q.back().first)
            q.pop_back();
        q.push_back(make_pair(dp[i],i));
        pair < int , int > fmm=q.front();

        while(!q.empty() && i>n+1 && q.front().second<i-n)
            q.pop_front();

        if(i>q.front().second && dp[i]-q.front().first>vmax)
        {
            vmax=dp[i]-q.front().first;
            st=q.front().second+1;
            l=i-q.front().second;
        }
    }
    g<<vmax<<" "<<st<<" "<<l<<'\n';
    f.close();
    g.close();
    return 0;
}