Cod sursa(job #766024)

Utilizator vendettaSalajan Razvan vendetta Data 10 iulie 2012 01:45:42
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.06 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

#define nmax 200005
#define inf (1<<30)
ifstream f("buline.in");
ofstream g("buline.out");

int a[2*nmax], n, s[2*nmax];
deque<int> dq;

void citeste(){

    f >> n;
    for(int i=1; i<=n; i++){
        int x, tip;
        f >> x >> tip;
        if (tip == 0) a[i] = -x;
                 else a[i] = x;
    }

    for(int j=1; j<=n; j++) a[j+n]=a[j];
}

void rezolva(){

    for(int i=1; i<=2*n; i++) s[i] = s[i-1] + a[i];
    int rez = -inf, st = 0, dr = 0;
    for(int i=1; i<=2*n; i++){
        while(dq.size() && i-dq.front()+1 > n) dq.pop_front();//scot secv de lungime mai mare ca si n
        while(dq.size() && s[i] < s[dq.back()]) dq.pop_back();
        dq.push_back(i);
        if (rez < s[i]-s[dq.front()]){
            rez = s[i]-s[dq.front()];
            st = dq.front()+1;
            dr = i;
        }
    }

    g << rez << " " << st << " "<< dr-st+1<<"\n";

}

int main(){

    citeste();
    rezolva();

    f.close();
    g.close();

}