Cod sursa(job #1527282)

Utilizator Nevermore10Macovei Cosmin Nevermore10 Data 17 noiembrie 2015 22:57:20
Problema Buline Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.99 kb
#include <fstream>
#include <deque>
#define NMAX 400010
using namespace std;
ifstream f("buline.in");
ofstream g("buline.out");
deque <int> d;
int v[NMAX] , suma[NMAX], maxim=-100000 ,n,semn, inceput, sfarsit;

int main() {
    f >> n;
    int val;
    for(int i = 0; i < n; i++) {
        f >> val >> semn;
        if(semn == 0) {
            v[i] = v[i+n] = -val;
        }
        else {
            v[i] = v[i+n] = val;
        }
        suma[i] = suma[i-1] + v[i];
    }
    for(int i = n; i < 2*n; i++) {
        suma[i] = suma[i-1] + v[i];
    }
    for(int i = 0; i < 2*n; i++) {
        while(!d.size() && suma[i] <= suma[d.back()]) {
            d.pop_front();
        }
        d.push_back(i);
        if(d.front() == i - n) {
            d.pop_front();
        }
        if(maxim < suma[i] - suma[d.front()]) {
            maxim = suma[i] - suma[d.front()];
            inceput = d.front()+1;
            sfarsit = i - d.front()-1;
        }
    }
    g << maxim << " " << inceput+1 << " " << sfarsit+1;
}