Pagini recente » Cod sursa (job #9340) | Cod sursa (job #1456088) | Cod sursa (job #1434872) | Cod sursa (job #1234252) | Cod sursa (job #2083603)
#include <iostream>
#include <fstream>
#include <deque>
#include <climits>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
int main()
{
deque<int> D;
int N, i, a, b, S, P, L;
f>>N;
int V[400010];
for(i=1; i<=N; i++){f>>a>>b;
if(b==1){V[i]=a;
V[i+N]=a;}
else{V[i]=-a;
V[i+N]=-a;}
}
for(i=2; i<=2*N; i++)V[i]=V[i-1]+V[i];
S=INT_MIN;
for(i=1; i<=2*N; i++)
{
while(D.size()>0 && V[D.back()]>V[i])D.pop_back();
D.push_back(i);
if(D.front()==i-N)D.pop_front();
if((V[i]-V[D.front()])>S)
{
S=V[i]-V[D.front()];
P=D.front()+1;
L=i-P+1;
}
}
g<<S<<" "<<P<<" "<<L;
return 0;
}