Cod sursa(job #921471)

Utilizator vendettaSalajan Razvan vendetta Data 21 martie 2013 00:03:12
Problema Buline Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>

using namespace std;

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

#define nmax 200005
#define ll long long
#define inf (1<<30)

int n, a[nmax], poz[nmax], dr[nmax];
int Rez, startA, Lung;

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

void faSol(int sum, int x, int y){
    int lung = y - x + 1; if (lung <= 0) lung += n;// pt circularitate
    if (sum > Rez){
        Rez = sum; startA = x; Lung = lung;
    }else if (sum == Rez){
        if (startA > x){
            startA = x; Lung = lung;
        }else if (startA == x){
            if (Lung > lung){
                Lung = lung;
            }
        }
    }
}

void bagaSsm(){
    Rez = -inf;
    int sum =0; int st = 1;
    for(int i=1; i<=n; ++i){
        if (sum + a[i] >= a[i]){// daca aduce profit
            sum = sum + a[i];
        }else sum = a[i], st = i;
        faSol(sum, st, i);// incepe in st, si se termina la i
    }
}

void rezolva(){
    // primaadata caut secventa cea mai buna din sir iar apoi pentru fiecare secventa 1..i leg cea mai buna secventa j..n(j > i)
    // astfel tratez circularitatea
    bagaSsm();
    // acum imi precalculez dr[i] = cea mai bun secventa ce se termina pe n din intervalul i...n
    int sum = 0;
    for(int i=n; i>=1; --i){
        sum += a[i];
        if (dr[i+1] > sum){
            dr[i] = dr[i+1]; poz[i] = poz[i+1];
        }else{
            dr[i] = sum; poz[i] = i;
        }
    }
    sum = 0;
    for(int i=1; i<n; ++i){
        sum += a[i]; faSol(sum + dr[i+1], poz[i+1], i);
        //cout << sum << " " << i << " " << dr[i+1] << "\n";
    }

    //cout << Rez << " " << startA << " " << Lung << "\n";
    g << Rez << " " << startA << " " << Lung << "\n";
}

int main(){
    citeste();
    rezolva();

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

    return 0;
}