Submission #1150813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150813		weakweakweak	Two Dishes (JOI19_dishes)	C++20	100 / 100	1527 ms	223932 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, m;
ll dura[1510000], revea[1510000], deadla[1510000], cuma[1510000]={0}; // duration, revenue, deadline, cumulative
ll durb[1510000], reveb[1510000], deadlb[1510000], cumb[1510000]={0}; 
ll qa[1510000], qb[1510000];
ll ans = 0;
vector<pair<int,long long>> v[1510000]; 

map<int, ll> mp;


void work (int pos, ll val) {
    auto it = mp.lower_bound(pos);
    while (val < 0) {
        pos = it->first;
        val += it->second;
        it = mp.erase(it);
    }
    mp[pos] += val;
}
 

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> dura[i] >> deadla[i] >> revea[i];
        cuma[i] = cuma[i-1] + dura[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> durb[i] >> deadlb[i] >> reveb[i];
        cumb[i] = cumb[i-1] + durb[i];
    }

    for (int i = 1; i <= n; i++) {
        if (cuma[i] > deadla[i]) continue;
        qa[i] = upper_bound(cumb+1, cumb+1+m, deadla[i]-cuma[i]) - cumb;
        ans += revea[i];
        if (qa[i] <= m) v[i].push_back(make_pair(-revea[i], qa[i]));
    } 
    for (int i = 1; i <= m; i++) {
        if (cumb[i] > deadlb[i]) continue;
        qb[i] = upper_bound(cuma+1, cuma+1+n, deadlb[i]-cumb[i]) - cuma;
        if (qb[i] <= n) v[qb[i]].push_back(make_pair(reveb[i], i));
        else ans += reveb[i]; // 一定拿的到
    }

    mp[0] = 0;
    mp[m+1] = LLONG_MAX/2;
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end()); reverse(v[i].begin(), v[i].end());
        for (auto [val, pos] : v[i]) work(pos, val);
        // for (auto z : mp) cout << z.first << ' ' << z.second << "  "; cout << '\n';
    }

    for (auto [pos, val] : mp) {
        if (pos != m+1) ans += val;
    }
    cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9