Submission #1150811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150811		weakweakweak	Two Dishes (JOI19_dishes)	C++20	0 / 100	153 ms	50020 KiB

dishes

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

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

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;
        if (val >= 0) break;
        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 (cumb[1]+cuma[i] > deadla[i]) qa[i] = 0;
        else qa[i] = upper_bound(cumb+1, cumb+1+n, deadla[i]-cuma[i]) - cumb;
        ans += revea[i];
        v[i].push_back(make_pair(-revea[i], qa[i]));
    }
    for (int i = 1; i <= m; i++) {
        if (cuma[1]+cumb[i] > deadlb[i]) qb[i] = 0;
        else qb[i] = upper_bound(cuma+1, cuma+1+m, deadlb[i]-cumb[i]) - cuma;
        v[qb[i]].push_back(make_pair(reveb[i], 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 [pos, val] : mp) {
        if (pos != m+1) ans += val;
    }
    cout << ans << '\n';
}

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