Submission #585893

#	Time	Username	Problem	Language	Result	Execution time	Memory
585893		Lucpp	Two Dishes (JOI19_dishes)	C++17	100 / 100	2152 ms	191504 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int MAX = 1e6+2;

ll A[2][MAX], T[2][MAX], P[2][MAX];
int n[2], B[2][MAX];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n[0] >> n[1];
    for(int i = 0; i < 2; i++){
        A[i][0] = 0;
        for(int j = 1; j <= n[i]; j++){
            cin >> A[i][j] >> T[i][j] >> P[i][j-1];
            A[i][j] += A[i][j-1];
        }
    }
    
    for(int i = 0; i < 2; i++){
        for(int j = 1; j <= n[i]; j++){
            if(A[i][j] > T[i][j]) B[i][j-1] = -1;
            else if(A[i][j]+A[1-i][n[1-i]] <= T[i][j]) B[i][j-1] = n[1-i];
            else B[i][j-1] = (int)(upper_bound(A[1-i], A[1-i]+n[1-i], T[i][j]-A[i][j])-A[1-i]-1);
            // cerr << B[i][j-1] << " ";
        }
        // cerr << "\n";
    }
    
    vector<vector<int>> todo(n[0]+2);
    ll sum = 0;
    for(int i = 0; i < n[1]; i++){
        if(B[1][i] > -1) todo[B[1][i]].push_back(i), sum += P[1][i];
    }

    map<int, ll> s;
    set<int> toCorrect;
    s.emplace(0, sum);
    auto correct = [&](int i){
        auto it = s.find(i);
        if(it == s.end() || it->second >= 0) return;
        ll x = it->second;
        while(true){
            it = s.erase(it);
            if(it == s.end()) break;
            it->second += x;
            if(it->second >= 0) break;
            x = it->second;
        }
    };
    auto upd = [&](int i, ll v){
        s[0] += v;
        s[i+1] += -v;
        // toCorrect.insert(0);
        toCorrect.insert(i+1);
    };
    for(int i = 0; i < n[0]; i++){
        toCorrect.clear();
        if(B[0][i] > -1) upd(B[0][i], P[0][i]);
        for(int j : todo[i]){
            upd(j, -P[1][j]);
        }
        for(int j : toCorrect) correct(j);
        // cerr << i << ":\n";
        // for(auto [j, x] : s){
        //     cerr << "   " << j << " " << x << "\n";
        // }
    }

    ll ans = 0;
    for(auto [i, x] : s) if(i <= n[1]) ans += x;
    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