Submission #1006268

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006268		devariaota	Cloud Computing (CEOI18_clo)	C++17	100 / 100	284 ms	1440 KiB

clo

#include <bits/stdc++.h>
using namespace std;

# define int long long
# define fir first
# define sec second
# define pb push_back
# define endl "\n"

const int cnst = 1e5+55;
bool mutipletestcase = 0;
//bool debug = false;

bool sorting(tuple<int, int, int, bool> a, tuple<int, int, int, bool> b) {
    auto[a1, a2, a3, a4] = a;
    auto[b1, b2, b3, b4] = b;
    if(a1 == b1) return a4 > b4;
    return a1 < b1;
}

void solve() {
    int n; cin >> n;

    vector<tuple<int, int, int, bool>> vec;

    for(int i = 1; i<=n; i++) {
        int a, b, c; cin >> a >> b >> c;
        vec.pb({b, a, c, 0});
    }

    int m; cin >> m;

    for(int i = 1; i<=m; i++) {
        int a, b, c; cin >> a >> b >> c;
        vec.pb({b, a, c, 1});
    }

    sort(vec.begin(), vec.end(), sorting);
    reverse(vec.begin(), vec.end());

    int dp[cnst]; dp[0] = 0;
    for(int i = 1; i<=1e5; i++) dp[i] = 1e18*-1;
    
    for(auto [pow, fre, cos, id]: vec) {
        if(!id) {
            for(int i = 1e5; i>=fre; i--) dp[i] = max(dp[i], dp[i-fre]-cos);
        }
        else {
            for(int i = 0; i<=1e5-fre; i++) dp[i] = max(dp[i], dp[i+fre]+cos);
        }

        // for(int i = 1; i<=10; i++) cerr << dp[i] << " "; cerr << endl;
    }

    int ans = 0;
    for(int i = 0; i<=1e5; i++) ans = max(ans, dp[i]);
    cout << ans << endl; 
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t = 1;
    if(mutipletestcase) cin >> t; 
    while(t--) solve();
}

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