Submission #1189762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189762		onbert	Two Dishes (JOI19_dishes)	C++20	10 / 100	10091 ms	68660 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, maxN = 4e6 + 5, INF = 1e16;
int n, m;
int a[maxn], S[maxn], P[maxn];
int b[maxn], T[maxn], Q[maxn];
vector<pair<int, int>> pre[maxn], suf[maxn];
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i=1;i<=n;i++) cin >> a[i] >> S[i] >> P[i];
    for (int i=1;i<=m;i++) cin >> b[i] >> T[i] >> Q[i];
    a[0] = b[0] = 0;
    for (int i=1;i<=n;i++) a[i] += a[i-1];
    for (int i=1;i<=m;i++) b[i] += b[i-1];
    a[n+1] = INF, b[m+1] = INF;
    for (int i=1;i<=n;i++) {
        int val = upper_bound(b, b+m+1, S[i] - a[i]) - b - 1;
        // cout << S[i] - a[i] << endl;
        if (val != -1) suf[val].push_back({i, P[i]});
        // cout << i << " " << val << endl;
    }
    for (int i=1;i<=m;i++) {
        int val = upper_bound(a, a+n+1, T[i] - b[i]) - a - 1;
        if (val != -1) pre[i].push_back({val, Q[i]});
        // cout << i << " " << val << endl;
    }
    int dp[n+1];
    for (int i=0;i<=n;i++) dp[i] = 0;
    for (int i=0;i<=m;i++) {
        for (auto [pos, val]:pre[i]) {
            for (int j=0;j<=pos;j++) dp[j] += val;
            // cout << "pre " << pos << " " << val << endl;
        }
        for (int j=1;j<=n;j++) dp[j] = max(dp[j-1], dp[j]);
        for (auto [pos, val]:suf[i]) {
            for (int j=pos;j<=n;j++) dp[j] += val;
            // cout << "suf " << pos << " " << val << endl;
        }
        // for (int j=0;j<=n;j++) cout << dp[j] << " "; cout << endl;
    }
    cout << dp[n] << "\n";
}

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