Cod sursa(job #2299473)

Utilizator radugheoRadu Mihai Gheorghe radugheo Data 9 decembrie 2018 17:04:00
Problema Buline Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 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;
};

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

solutie sol1, sol2, ssm;

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 (sol1.val < s){
            sol1.val = s;
            sol1.l2 = i;
            sol1.l1 = i - cnt + 1;
        }
        else{
            cnt++;
        }
    }
    for (i=1; i<=n; i++){ /// in cazul in care iau in calcul ca sirul este 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];
        t[i] = max (t[i-1], sp[i]);
    }
    cnt = 0;
    for (i=1; i<=n; i++){
        if (sol2.val < t[i-1] + sp[n] - sp[i-1]){
            sol2.val = t[i-1] + sp[n] - sp[i-1];
            sol2.l2 = i;
            sol2.l1 = i - cnt + 1;
        }
        else{
            cnt++;
        }
    }
    ssm = ((sol1.val > sol2.val) ? sol1 : sol2);
    fout << ssm.val << " " << ssm.l1 << " " << ssm.l2;
    return 0;
}