Submission #1320793

#TimeUsernameProblemLanguageResultExecution timeMemory
1320793khanhphucscratchCloud Computing (CEOI18_clo)C++20
100 / 100
428 ms2240 KiB
#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[2][100005];
struct Thing
{
    int c, f, v;
    int type;
    Thing(int c, int f, int v, int type): c(c), f(f), v(v), type(type){}
};
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    vector<Thing> st;
    int n; cin>>n;
    for(int i = 1; i <= n; i++){
        int c, f, v; cin>>c>>f>>v;
        st.emplace_back(c, f, v, 0);
    }
    int m; cin>>m;
    for(int i = 1; i <= m; i++){
        int c, f, v; cin>>c>>f>>v;
        st.emplace_back(c, f, v, 1);
    }
    sort(st.begin(), st.end(), [&](Thing &x, Thing &y){return x.f > y.f || (x.f == y.f && x.type < y.type);});
    int sum = n*50;
    for(int i = 1; i <= sum; i++) dp[0][i] = -1e18;
    for(int i = 0; i < st.size(); i++){
        int u = i%2, v = (u^1);
        for(int j = 0; j <= sum; j++){
            dp[v][j] = dp[u][j];
            if(st[i].type == 0){
                if(j >= st[i].c) dp[v][j] = max(dp[v][j], dp[u][j-st[i].c] - st[i].v);
            }
            else{
                if(j+st[i].c <= sum) dp[v][j] = max(dp[v][j], dp[u][j+st[i].c] + st[i].v);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i <= sum; i++) ans = max(ans, dp[st.size()%2][i]);
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...