Cod sursa(job #766014)

Utilizator vendettaSalajan Razvan vendetta Data 10 iulie 2012 00:52:38
Problema Buline Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <deque>

using namespace std;

#define nmax 200005

ifstream f("buline.in");
ofstream g("buline.out");

int a[2*nmax], n;
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(){
    int sum = 0, rez=0, st=0, dr=0;

    for(int i=1; i<=2*n-1; i++){
        if (sum + a[i] > a[i]){
            if (i-dq.front()+1 <= n){
                dq.push_back(i);
                sum += a[i];
                if (sum > rez){
                    rez = sum;
                    st = dq.front();
                    dr = i;
                }
            }else{
                if (sum > rez){
                    rez = sum;
                    st = dq.front();
                    dr = i-1;
                }
                sum -= a[dq.front()];
                dq.pop_front();
                dq.push_back(i);
                sum += a[i];
                if (sum > rez){
                    rez = sum;
                    st = dq.front();
                    dr = i;
                }
            }
        }else{
            if (sum > rez){
                st = dq.front();
                dr = i-1;
            }
            dq.clear();
            sum = a[i];
            dq.push_back(i);
            if(sum > rez){
                st = dq.front();
                dr = i;
            }
        }
    }

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

}


int main(){

    citeste();
    rezolva();

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

}