Cod sursa(job #2765394)

Utilizator DragosC1Dragos DragosC1 Data 26 iulie 2021 18:20:12
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
using namespace std;

int n;
int v[200001];

void read() {
    int x, y, i;
    ifstream f("buline.in");
    f >> n;
    for (i = 1; i <= n; i++) {
        f >> x >> y;
        if (y == 1)
            v[i] = x;
        else v[i] = -x;
    }
    f.close();
}

int st, L;
int Max = -2e9 - 1;

int sp[200001];

void solve() {
    int i, S, first, l;

    // momentam nu tratam circularitatea
    first = 1;
    S = 0;
    for (i = 1; i <= n; i++) {
        S += v[i];
        if (S > Max) {
            Max = S;
            l = i - first + 1; 
        }
        if (S < 0) {
            first = i + 1;
            S = 0;
        }
    }

    st = first, L = l;

    // tratam circularitatea
    for (i = 1; i <= n; i++)
        sp[i] = sp[i - 1] + v[i];

    int last, cMax = -2e9 - 1;
    for (i = 1; i <= n - 1; i++) {
        if (sp[i] > cMax) {
            cMax = sp[i];
            first = i;
        }
        if (cMax + sp[n] - sp[i] > Max) {
            Max = cMax + sp[n] - sp[i];
            st = i + 1;
            L = first + (n - i);
        }
    }
}

void output() {
    ofstream g("buline.out");
    g << Max << ' ' << st << ' ' << L;
    g.close();
}

int main() {
    read();
    solve();
    output();
    return 0;
}