Pagini recente » Cod sursa (job #1792370) | Cod sursa (job #97708) | Cod sursa (job #2137767) | Cod sursa (job #1301016) | Cod sursa (job #2549963)
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("buline.in");
ofstream fout("buline.out");
long long int n,i,x,b,maxi, s, du, p, u;
long long int v[500001], d[500001];
int main()
{
fin>>n;
for (i=1; i<=n; i++)
{
fin>>x>>b;
if (b==0)
x = -x;
v[i] = v[i-1] + x;
v[i+n]=x;
}
for (i=n+1; i <= 2*n; i++)
v[i] += v[ i-1 ] ;
p=1;
d[++u]=0;
for (i=1; i<=n*2; i++)
{
while ( p<=u && v[i] < v[ d[u] ] )
u--;
d[++u] = i;
if ( i - d[p] - 1 == n )
p++;
if ( v[i] - v[ d[p] ] > maxi)
{
maxi = v[i] - v[ d[p] ];
s = d[p];
du = i - s;
}
}
fout<< maxi <<" "<< s+1 <<" "<< du ;
return 0;
}