Submission #1311647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311647		Sunbae	Cloud Computing (CEOI18_clo)	C++20	100 / 100	468 ms	2120 KiB

clo

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[2][50*2001];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, mx = 0; cin>>n;
    vector<tuple<int,int,int,int>> a;
    a.emplace_back((int)-2e9, (int)-2e9, (int)-2e9, (int)-2e9);
    for(int i = 0, c, f, v; i<n; ++i){
        cin>>c>>f>>v;
        a.emplace_back(-f, 0, c, v); mx += c;
    }
    int m; cin>>m;
    for(int i = 0, c, f, v; i<m; ++i){
        cin>>c>>f>>v;
        a.emplace_back(-f, 1, c, v);
    }
    sort(a.begin(), a.end());
    fill(dp[0], dp[0]+mx+1, (ll)-1e15);
    dp[0][0] = 0;
    for(int i = 1; i<a.size(); ++i){
        int I = i&1, II = (i-1)&1, c = get<2>(a[i]), v = get<3>(a[i]);
        for(int j = 0; j<=mx; ++j) dp[I][j] = dp[II][j];
        if(!get<1>(a[i])){
            for(int j = mx; ~j && j>=c; --j){
                dp[I][j] = max(dp[I][j], dp[II][j-c] - v);
            }   
        }else{
            for(int j = 0; j+c<=mx; ++j){
                dp[I][j] = max(dp[I][j], dp[II][j+c] + v);
            }
        }      
    }
    cout<<*max_element(dp[(a.size()-1)&1], dp[(a.size()-1)&1]+mx+1);
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10