Submission #1336614

#TimeUsernameProblemLanguageResultExecution timeMemory
1336614sh_qaxxorov_571금 캐기 (IZhO14_divide)C++20
100 / 100
23 ms8028 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Mine {
    ll x, g, d;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    if (!(cin >> n)) return 0;

    vector<Mine> mines(n);
    for (int i = 0; i < n; i++) {
        cin >> mines[i].x >> mines[i].g >> mines[i].d;
    }

    // Prefiks summalar: oltin va (energiya - koordinata farqi)
    vector<ll> prefix_gold(n + 1, 0);
    vector<ll> p(n + 1, 0);

    for (int i = 0; i < n; i++) {
        prefix_gold[i + 1] = prefix_gold[i] + mines[i].g;
        // p[i] qiymati: jami energiya - oxirgi koordinata
        p[i + 1] = p[i] + mines[i].d;
    }

    // Har bir i uchun qiymat: Energiya_sum(1..i) - x[i]
    vector<ll> val(n + 1);
    for (int i = 1; i <= n; i++) {
        val[i] = p[i] - mines[i - 1].x;
    }
    
    // x[i] - Energiya_sum(1..i-1) qiymati bo'yicha eng kichik nuqtani topish
    // Shart: val[j] >= Energiya_sum(1..i-1) - x[i]
    vector<ll> start_val(n + 1);
    for (int i = 1; i <= n; i++) {
        start_val[i] = p[i - 1] - mines[i - 1].x;
    }

    ll max_gold = 0;
    vector<pair<ll, int>> s; // Monotonik stek yoki saralangan vektor
    for (int i = 1; i <= n; i++) {
        // start_val[i] ni kiritish (eng kichiklarini saqlash)
        if (s.empty() || start_val[i] < s.back().first) {
            s.push_back({start_val[i], i});
        }
        
        // Binary search orqali shartni qanoatlantiruvchi eng chap i ni topish
        // val[i] >= start_val[k]
        int l = 0, r = s.size() - 1, best_idx = i;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (s[mid].first <= val[i]) {
                best_idx = s[mid].second;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        max_gold = max(max_gold, prefix_gold[i] - prefix_gold[best_idx - 1]);
    }

    cout << max_gold << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...