Cod sursa(job #1457973)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 5 iulie 2015 12:20:24
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream f("buline.in");
ofstream g("buline.out");

deque<int> Q;
int a[400005],i,n,ans,start,stop;

int main()
{
    f>>n;
    for(i=1;i<=n;++i)
    {
       f>>a[i]>>ans;
       if(ans==0) a[i]*=(-1);
    }
    for(i=n+1;i<2*n;++i) a[i]=a[i-n];
    for(i=1;i<2*n;++i) a[i]+=a[i-1];

    ans=a[1];start=stop=1;
    Q.push_back(a[1]);

    for(i=2;i<2*n;++i)
    {
        if(Q.front()<i-n) Q.pop_front();

        while(Q.size() && a[i]<a[Q.back()]) Q.pop_back();

        if(Q.size() && a[i]-a[Q.front()]>ans)
        {
            ans=a[i]-a[Q.front()];
            start=Q.front()+1;
            stop=i;
        }
        Q.push_back(i);
    }
    g<<ans<<' '<<start<<' '<<stop-start+1<<'\n';
    return 0;
}