Pagini recente » Cod sursa (job #1342958) | Cod sursa (job #1527399) | Cod sursa (job #1898086) | Cod sursa (job #1065971) | Cod sursa (job #1984884)
#include <cstdio>
using namespace std;
int n, a[200002], dq[200002], Sum[200002];
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];
}
int Front = 1, Back = 0, Max = -200000000, L = 0, pos = 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 && Back >= Front) ++Front;
dq[++Back] = i;
}
printf("%d %d %d", Max, pos, L);
return 0;
}