제출 #1170993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1170993		patgra	Two Dishes (JOI19_dishes)	C++20	10 / 100	85 ms	31816 KiB

dishes

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back
#define int ll

using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, pair<int, int>>> a(n), b(m);
    rep(i, 0, n) cin >> a[i].first >> a[i].second.first >> a[i].second.second;
    rep(i, 0, m) cin >> b[i].first >> b[i].second.first >> b[i].second.second;
    bool subtask1 = true;
    rep(i, 1, n) if(a[i].second.first != a[i - 1].second.first) subtask1 = false;
    if(a.back().second.first != b[0].second.first) subtask1 = false;
    rep(i, 1, m) if(b[i].second.first != b[i - 1].second.first) subtask1 = false;
    if(subtask1) {
        vector<int> psB(m + 1, 0), psB2(m + 1, 0);
        rep(i, 0, m) psB[i + 1] = psB[i] + b[i].first;
        rep(i, 0, m) psB2[i + 1] = psB2[i] + b[i].second.second;
        int iGet = 0, myTime = 0, lastTime = a[0].second.first;
        int ans = -1e18;
        rep(i, 0, n + 1) {
            int where = ranges::upper_bound(psB, lastTime - myTime) - psB.begin() - 1;
            if(where < 0) where = 0;
            ans = max(ans, iGet + psB2[where]);
            DC << i << ' ' << where << "  " << iGet << "+" << psB2[where] << eol;
            if(i == n) continue;
            myTime += a[i].first;
            iGet += a[i].second.second;
        }
        cout << ans << '\n';
        return 0;
    }
    if(n <= 2000 && m <= 2000) {
        vector<ll> psA(n + 1, 0), psB(m + 1, 0);
        rep(i, 0, n) psA[i + 1] = psA[i] + a[i].first;
        rep(i, 0, m) psB[i + 1] = psB[i] + b[i].first;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
        rep(i, 0, n + 1) rep(j, 0, m + 1) {
            if(j + 1 <= m) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + (int)(psA[i] + psB[j + 1] <= b[j].second.first) * b[j].second.second);
            if(i + 1 <= n) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + (int)(psA[i + 1] + psB[j] <= a[i].second.first) * a[i].second.second);
        }
        cout << dp[n][m] << '\n';
        return 0;
    }
}

• 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