Pagini recente » Cod sursa (job #295758) | Cod sursa (job #2828378) | Cod sursa (job #2821723) | Cod sursa (job #456392) | Cod sursa (job #1984888)
#include <cstdio>
using namespace std;
long long n, a[400002], dq[400002], Sum[400002];
int main()
{
freopen("buline.in", "r", stdin);
freopen("buline.out", "w", stdout);
scanf("%d", &n);
bool ok = 0;
for(int i = 1; i <= n ; ++i){
scanf("%d%d", &a[i], &ok);
if(ok == 0) a[i] = -a[i];
a[n + i] = a[i];
}
long long Front = 1, Back = 0, Max = -200000000, L = 0, pos = 0;
dq[++Back] = 0;
for(int i = 1; i <= n * 2; ++i){
Sum[i] = Sum[i - 1] + a[i];
while(Back >= Front && Sum[i] <= Sum[dq[Front]])
--Back;
if(Sum[i] - Sum[dq[Front]] > Max) {
Max = Sum[i] - Sum[dq[Front]];
L = i - dq[Front];
pos = dq[Front] + 1;
}
if(dq[Front] <= i - n) ++Front;
dq[++Back] = i;
}
printf("%lld %lld %lld", Max, pos, L);
return 0;
}