Cod sursa(job #3236965)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 3 iulie 2024 19:41:16
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#include <queue>
#include <cmath>
#define ll long long
#define ld long double

std::ifstream cin("buline.in");
std::ofstream cout("buline.out");

const int NMAX = 2e5;
const int INF = 2e9;

struct Triplet {
    int max_sum, left, length;
    bool operator < (const Triplet &other) const {
        if(max_sum > other.max_sum) {
            return true;
        }
        if(max_sum == other.max_sum && left < other.left) {
            return true;
        }
        if(max_sum == other.max_sum && left == other.left && length < other.length) {
            return true;
        }
        return false;
    }
};

int n, sum, max_sum, start, left, length;
int a[NMAX + 1];
Triplet dp_prefix[NMAX + 5], dp_suffix[NMAX + 5];
Triplet answer;

int main() {
    std::ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = (y == 1 ? x : -x);
    }

    max_sum = -INF;
    sum = 0;
    start = 1;
    left = 0;
    length = 0;
    answer = {max_sum, left, length};
    for(int i = 1; i <= n; i++) {
        sum += a[i];
        if(sum > max_sum) {
            max_sum = sum;
            left = start;
            length = i - left + 1;
        }
        if(sum < 0) {
            sum = 0;
            start = i + 1;
        }
        answer = std::min(answer, {max_sum, left, length});
    }

    sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += a[i];
        dp_prefix[i] = std::min(dp_prefix[i - 1], {sum, 1, i});
    }

    sum = 0;
    for(int i = n; i >= 1; i--) {
        sum += a[i];
        dp_suffix[i] = std::min(dp_suffix[i + 1], {sum, i, n - i + 1});
    }

    for(int i = 1; i <= n - 1; i++) {
        answer = std::min(answer, {dp_prefix[i].max_sum + dp_suffix[i + 1].max_sum, dp_suffix[i + 1].left, dp_prefix[i].length + dp_suffix[i + 1].length});
    }
    cout << answer.max_sum << ' ' << answer.left << ' ' << answer.length << '\n';


    return 0;
}