Cod sursa(job #2961742)

Utilizator rastervcrastervc rastervc Data 6 ianuarie 2023 22:03:53
Problema Buline Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <climits>

using namespace std;

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

constexpr size_t LIM = 200005;
int N, i, a, b, arr[LIM], sum;
int max_sum, start, finish;

int main() {
    max_sum = INT_MIN;

    fin >> N;
    for (i = 0; i < N; ++i) {
        fin >> a >> b;
        if (b == 0) arr[i] = -a;
        else arr[i] = a;
    }

    deque<pair<int, int>> deq;
    for (i = 0; i < N - 1; ++i) {
        sum += arr[i];
        while (!deq.empty() && sum < deq.back().second)
            deq.pop_back();
        deq.emplace_back(i, sum);
    }

    for (int j = 0; j < N; ++j, ++i) {
        if (deq.front().first == i - N)
            deq.pop_front();

        sum += arr[i % N];
        const int min_sum = deq.front().second;
        if (sum - min_sum > max_sum) {
            max_sum = sum - min_sum;
            start = (deq.front().first + 1) % N;
            finish = i % N;
        }

        while (!deq.empty() && sum < deq.back().second)
            deq.pop_back();
        deq.emplace_back(i, sum);
    }

    int len = finish - start + 1;
    if (len <= 0) len += N;
    fout << max_sum << ' ' << start + 1 << ' ' << len;

    fin.close();
    fout.close();
    return 0;
}