Cod sursa(job #1571325)

Utilizator Master011Dragos Martac Master011 Data 17 ianuarie 2016 21:04:47
Problema Buline Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#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;
}