Submission #598288

#	Time	Username	Problem	Language	Result	Execution time	Memory
598288		1bin	Cloud Computing (CEOI18_clo)	C++14	100 / 100	486 ms	1368 KiB

clo

#include <bits/stdc++.h>
 
using namespace std;
 
#define all(v) v.begin(), v.end()
typedef long long ll;
const int MAX = 1e5 + 5;
struct t{
    ll c, f, p;
    bool operator <(const t & x){
        if(f == x.f) return p < x.p;
        return f > x.f;
    }
};
ll n, m, c, f, p, dp[MAX];
vector<t> v;
 
int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
    cin >> n;
    while(n--){
        cin >> c >> f >> p;
        v.push_back({c, f, -p});
    }
    cin >> m;
    while(m--){
        cin >> c >> f >> p;
        v.push_back({c, f, p});
    }
    sort(all(v));
    for(int i = 1; i < MAX; i++) dp[i] = -1e18;
    
    for(auto& x : v){
        if(x.p < 0){
            for(int i = MAX - 1; i >= x.c; i--)
                dp[i] = max(dp[i], dp[i - x.c] + x.p);
        }
        else{
            for(int i = 0; i + x.c < MAX; i++)
                dp[i] = max(dp[i], dp[i + x.c] + x.p);
        }
    }
    ll ans = 0;
    for(int i = 0; i < MAX; i++) ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}

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