Cod sursa(job #1388555)

Utilizator otto1Palaga Vicentiu-Octavian otto1 Data 15 martie 2015 15:56:00
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("buline.in");
ofstream fo("buline.out");
const int nmax =4e5 + 5;
int s[nmax];
deque < int > q;
int main(void)
{
    int n,ans=0,p,u;
    int x,y;
    fi>>n;
    for (int i=1;i<=n;++i) fi >> x >> y,s[i] =(!y ? -x : x) + s[i-1];
    for (int i=1;i<=n;++i) s[n+i]=s[n+i-1] + s[i] - s[i-1];
    q.push_back(0);
    for (int i=1;i<=n+n;++i)
    {
        while (!q.empty() && s[i] <= s[q.back()]) q.pop_back();
        q.push_back(i);
        while (!q.empty() && i-n > q.front()) q.pop_front();
        if (!q.empty() && s[i] - s[q.front()] > ans) ans = s[i] - s[q.front()],p=q.front()+1,u=i;
    }
    return fo << ans << ' ' << p << ' ' << u-p+1 << '\n',0;
}