Pagini recente » Cod sursa (job #586179) | Cod sursa (job #2322710) | Cod sursa (job #1717053) | Cod sursa (job #2253221) | Cod sursa (job #1408859)
#include <cstdio>
#include <algorithm>
#include <deque>
#define NMAX 200005
using namespace std;
deque <int> d;
int v[2*NMAX],s[2*NMAX];
void print() {
for(int i=0; i<d.size(); i++)
printf("%d ",d[i]);
printf("\n");
}
int main() {
int n,x,y,sol=-NMAX,p,q;
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
scanf("%d",&n);
for(int i=1; i<=n; i++) {
scanf("%d%d",&x,&y);
v[i]=x;
if(!y)
v[i]*=-1;
v[n+i]=v[i];
}
p=0;
d.push_front(0);
for(int i=1; i<=2*n-1; i++) {
s[i]=s[i-1]+v[i];
while ( (!d.empty()) && (s[d.back()]>s[i]) ) {
d.pop_back();
}
d.push_back(i);
if (i-d.front()>n) {
d.pop_front();
}
if (s[d.front()]>0) {
if (s[i]>sol && i<=n) {
sol=s[i],p=1,q=i;
continue;
}
}
if (s[i]-s[d.front()]>sol)
sol=s[i]-s[d.front()],p=d.front()+1,q=i-d.front();
}
printf("%d %d %d",sol,p,q);
}