Cod sursa(job #3244578)

Utilizator Manolea_Teodor_StefanManolea Teodor Stefan Manolea_Teodor_Stefan Data 25 septembrie 2024 17:00:38
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <bits/stdc++.h>

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

using ll = long long;

int n;
vector<int> v(200001);
vector<bool> hasBeenStart(200001);

struct a {
    ll value;
    int index;
    int length;
} curr, ans, ans2;

int main() {
    fin >> n;
    for (int i = 1; i <= n; i++) {
        short type;
        fin >> v[i] >> type;
        if (!type) {
            v[i] *= -1;
        }
    }

    curr = ans = {v[1],1,1};
    hasBeenStart[1] = true;

    for (int i = 2; curr.length < n; i++, i = i > n ? 1 : i) {
        if (curr.value + v[i] >= v[i]) {
            curr.length++;
            curr.value += v[i];
            if (ans.value < curr.value) {
                ans = curr;
            } else if (ans.value == curr.value and (ans.length < curr.length or ans.index < curr.index)) {
                ans = curr;
            }
        } else {
            curr.value = v[i];
            curr.length = 1;
            curr.index = i;
            if (hasBeenStart[i] == true) {
                break;
            }
            hasBeenStart[i] = true;
            if (ans.value < curr.value) {
                ans = curr;
            } else if (ans.value == curr.value and (ans.length < curr.length or ans.index < curr.index)) {
                ans = curr;
            }
        }
    }

    curr = ans2 = {v[1],1,1};
    hasBeenStart = vector<bool>(200001, false);
    hasBeenStart[1] = true;

    for (int i = 2; curr.length < n; i++, i = i > n ? 1 : i) {
        if (curr.value + v[i] <= v[i]) {
            curr.length++;
            curr.value += v[i];
            if (ans2.value > curr.value) {
                ans2 = curr;
            } else if (ans2.value == curr.value and (ans2.length > curr.length or ans2.index > curr.index)) {
                ans2 = curr;
            }
        } else {
            curr.value = v[i];
            curr.length = 1;
            curr.index = i;
            if (hasBeenStart[i] == true) {
                break;
            }
            hasBeenStart[i] = true;
            if (ans2.value > curr.value) {
                ans2 = curr;
            } else if (ans2.value == curr.value and (ans2.length > curr.length or ans2.index > curr.index)) {
                ans2 = curr;
            }
        }
    }
    int s = 0;
    for (int i = 1; i < ans2.index; i++) {
        s += v[i];
    }
    for (int i = ans2.index + ans2.length; i <= n; i++) {
        s += v[i];
    }
    if (ans.value < s) {
        ans.value = s;
        ans.index = ans2.index + ans2.length;
        ans.length = n - ans2.length;
    }

    fout << ans.value << ' ' << ans.index << ' ' << ans.length;

    return 0;
}