Submission #1294912

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294912		azamurai	Bigger segments (IZhO19_segments)	C++20	0 / 100	1 ms	560 KiB

segments

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    if (!(cin >> N)) return 0;
    vector<long long> a(N);
    for (int i=0;i<N;i++) cin >> a[i];

    vector<long long> seg; // суммы готовых сегментов
    long long last = 0;    // сумма предыдущего сегмента (для первого = 0)
    long long current = 0; // накапливаемая сумма текущего кандидата

    for (int i = 0; i < N; ++i) {
        current += a[i];
        if (current >= last) {
            seg.push_back(current);
            last = current;
            current = 0;
        }
    }

    // если остался хвост — присоединим к последнему сегменту
    if (current > 0) {
        if (seg.empty()) {
            // должно быть не пусто, но на всякий случай
            seg.push_back(current);
        } else {
            seg.back() += current;
        }
    }

    // теперь убедимся, что последовательность сумм не убывает:
    // если есть нарушение (последняя < предыдущей), то объединяем последние два и проверяем снова
    while (seg.size() >= 2) {
        int m = seg.size();
        if (seg[m-1] < seg[m-2]) {
            seg[m-2] += seg[m-1];
            seg.pop_back();
        } else break;
    }

    cout << seg.size() << '\n';
    return 0;
}

• Subtask 1: 0 / 13
• Subtask 2: 0 / 14
• Subtask 3: 0 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27