Pagini recente » Cod sursa (job #2681231) | Rating shibly (inam) | Monitorul de evaluare | Cod sursa (job #1968637) | Cod sursa (job #81391)
Cod sursa(job #81391)
#include <cstdio>
#define MAX 200001
#define max(a, b) (((a) > (b))?(a):(b))
FILE *in = fopen("buline.in","r"), *out = fopen("buline.out","w");
int n;
int a[MAX << 1];
int s[MAX << 1];
int st = 1, dr = 0;
int dq[MAX];
void read()
{
fscanf(in, "%d", &n);
int b = 0;
for ( int i = 1; i <= n; ++i )
{
fscanf(in, "%d %d", &a[i], &b);
if ( b == 0 )
a[i] *= -1;
}
for ( int i = 1; i < n; ++i )
a[n+i] = a[i];
s[1] = a[1];
for ( int i = 2; i < 2*n - 1; ++i )
s[i] = s[i-1] + a[i];
}
int main()
{
read();
int best = -1000000000;
int p = 1;
int l = 1;
for ( int i = 1; i < 2*n - 1; ++i )
{
if ( i - dq[st] > n )
++st;
while ( st <= dr && s[ dq[dr] ] >= s[i] )
--dr;
dq[++dr] = i;
if ( s[i] - s[ dq[st] ] > best )
{
best = s[i] - s[ dq[st] ];
p = dq[st] + 1;
l = i - p + 1;
}
}
fprintf(out, "%d %d %d\n", best, p, l);
return 0;
}