Pagini recente » Cod sursa (job #2021057) | Diferente pentru onis-2016/solutii-runda-1 intre reviziile 12 si 13 | Monitorul de evaluare | Istoria paginii utilizator/dursinaalexandru | Cod sursa (job #1809969)
#include <cstdio>
#define NMax 200000
#define ll long long
ll sum[2*NMax+1];
int deque[2*NMax+1];
int v[2*NMax+1];
int N;
void Read()
{
int i,x,t;
scanf("%d",&N);
for(i = 1; i <= N; ++i)
{
scanf("%d %d",&x,&t);
if(t) v[i] = x;
else v[i] = -x;
}
for(i = N+1; i <= 2*N; ++i) v[i] = v[i-N];
for(i = 1; i <= 2*N; ++i) sum[i] = sum[i-1] + v[i];
}
int main(){
freopen("buline.in","r",stdin);
freopen("buline.out","w",stdout);
int i,inc,sf,S,P,L;
Read();
inc = 0;
sf = 0;
for(S = -NMax, i = 1; i <= N; ++i)
{
if( sum[i] - sum[ deque[inc] ] > S ) { S = sum[i] - sum[ deque[inc] ]; P = deque[inc] + 1; L = i - P + 1; }
while( sf>=inc && sum[i] < sum[ deque[sf] ] ) --sf;
deque[++sf] = i;
}
if( !deque[inc] ) ++inc;
for(i = N+1; i <= 2*N; ++i)
{
if( sum[i] - sum[ deque[inc] ] > S ) { S = sum[i] - sum[ deque[inc] ]; P = deque[inc] + 1; L = i - P + 1; }
while( sf>=inc && deque[inc] <= i-N ) ++inc;
while( sf>=inc && sum[i] < sum[ deque[sf] ] ) --sf;
deque[++sf] = i;
}
printf("%d %d %d\n",S,P,L);
return 0;
}