Cod sursa(job #2930886)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 29 octombrie 2022 19:10:05
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>

using namespace std;
int constexpr maxN = 200010;
int v[maxN], s[maxN], smax[maxN], st[maxN], D[maxN], str[maxN];

int n, x, sol = -1e9, nr, L;

int main() {
    ifstream fin("buline.in");
    ofstream fout("buline.out");
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> v[i] >> x;
        if (x == 0) {
            v[i] = -v[i];
        }
        if (D[i - 1] + v[i] > v[i]) {
            D[i] = D[i - 1] + v[i];
            str[i] = str[i - 1];
        } else {
            D[i] = v[i];
            str[i] = i;
        }
        if (D[i] > sol) {
            sol = D[i];
            nr = str[i];
            L = i - str[i] + 1;
        }
    }
    s[1] = v[1];
    smax[1] = v[1];
    for (int i = 2; i <= n; i++) {
        s[i] = s[i - 1] + v[i];
        smax[i] = max(smax[i - 1], s[i]);
        if (smax[i - 1] > s[i]) {
            smax[i] = smax[i - 1];
            st[i] = st[i - 1];
        } else {
            smax[i] = s[i];
            st[i] = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (sol < smax[i - 1] + s[n] - s[i - 1]) {
            sol = smax[i - 1] + s[n] - s[i - 1];
            nr = i;
            L = st[i - 1] + n - i + 1;
        }
    }
    fout << sol << " " << nr << " " << L;
    return 0;
}