Pagini recente » Cod sursa (job #751) | Cod sursa (job #2744040) | Cod sursa (job #810933) | Cod sursa (job #945542) | Cod sursa (job #1571325)
#include<cstdio>
using namespace std;
const int nMax = 200001;
int dq[nMax], v[nMax];
int main (){
FILE *in = fopen("buline.in","r");
FILE *out = fopen("buline.out","w");
int n;
fscanf(in,"%d", &n);
for(int i = 1, sgn; i <= n ; ++i){
fscanf(in,"%d%d", &v[i], &sgn);
if(!sgn) v[i] = -v[i];
v[n + i] = v[i];
}
int sol = -10001, st = 1, dr = 0, poz, l;
for(int i = 1, j = 0; i <= 2 * n ; ++i, ++j){
v[i] += v[i - 1];
while(st <= dr && v[dq[dr]] >= v[j])
dr--;
dq[++dr] = j;
if(st <= dr && dq[st] <= j - n)
st++;
if(sol < v[i] - v[dq[st]]){
sol = v[i] - v[dq[st]];
poz = dq[st] + 1;
l = i - poz + 1;
}
}
fprintf(out,"%d %d %d\n", sol, poz, l);
return 0;
}