Pagini recente » Cod sursa (job #2837283) | Cod sursa (job #2911195) | Cod sursa (job #3148407) | Cod sursa (job #1007454) | Cod sursa (job #2413326)
#include <fstream>
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
long long n,i,x,val,maxi, v[500000], d[500000], start, durata, p, u;
int main()
{
f>>n;
for (i=1; i<=n; i++) {
f>>x>>val;
if (!val) 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] ];
start = d[p];
durata = i - start;
}
}
g<< maxi <<" "<< start+1 <<" "<< durata ;
return 0;
}