Cod sursa(job #2930882)

Utilizator mihaistamatescuMihai Stamatescu mihaistamatescu Data 29 octombrie 2022 18:55:17
Problema Buline Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>

using namespace std;
int constexpr maxN = 200010;
int v[maxN], s[maxN], smax[maxN], st[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];
        }
    }
    for (int i = 1; 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;
}