Cod sursa(job #2299491)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 9 decembrie 2018 17:17:58
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <fstream>
#define DIM 200005

using namespace std;

ifstream fin  ("buline.in");
ofstream fout ("buline.out");

struct solutie {
    int val;
    int l1;
    int l2;
};

int n, i, b, s, cnt;
int v[DIM], t[DIM], sp[DIM], ind[DIM];

solutie sol;

int main(){
    fin >> n;
    for (i=1; i<=n; i++){
        fin >> v[i] >> b;
        if (b == 0)
            v[i] = -v[i];
    }
    for (i=1; i<=n; i++){ /// in cazul in care nu luam in calcul ca sirul este circular
        s = max (s + v[i], v[i]);
        if (sol.val < s){
            sol.val = s;
            sol.l2 = i;
            sol.l1 = i - cnt + 1;
            cnt = 0;
        }
        else{
            cnt++;
        }
    }
    for (i=1; i<=n; i++){ /// daca luam sirul circular, calculez cea mai buna secventa de tipul i, i+1, ..., n-1, n, 1, 2, ..., j-1, j
        sp[i] = sp[i-1] + v[i];
        if (t[i-1] > sp[i]){
            t[i] = t[i-1];
            ind[i] = ind[i-1];
        }
        else{
            t[i] = sp[i];
            ind[i] = i;
        }
    }
    for (i=1; i<=n; i++){
        if (sol.val < t[i-1] + sp[n] - sp[i-1]){
            sol.val = t[i-1] + sp[n] - sp[i-1];
            sol.l1 = i;
            sol.l2 = n + ind[i-1] - i + 1;
        }
        else{
            cnt++;
        }
    }
    fout << sol.val << " " << sol.l1 << " " << sol.l2;
    return 0;
}