제출 #787145

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
787145		c2zi6	Cloud Computing (CEOI18_clo)	C++14	100 / 100	948 ms	3712 KiB

clo

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

struct NODE {
    ll w;
    ll f;
    ll v;
    bool operator<(const NODE& b) {
        if (this->f == b.f) return this->w > b.w;
        return this->f > b.f;
    }
};

const ll MAXW = 4000 * 50 + 100;

void solve() {
    ll N, M;
    vector<NODE> a;
    cin >> N;
    for (int i = 0; i < N; i++) {
        ll c, f, v;
        cin >> c >> f >> v;
        a.push_back({c, f, -v});
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        ll c, f, v;
        cin >> c >> f >> v;
        a.push_back({-c, f, v});
    }
    sort(a.begin(), a.end());
    //for (auto x : a) cout << x.w << " " << x.v << endl;
    ll n = a.size();
    ll dp[2][MAXW];
    for (int i = 0; i < MAXW; i++) dp[0][i] = -1e18;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        ll v = a[i-1].v;
        ll w = a[i-1].w;
        
        int cur = i%2;
        int prev = !cur;
        
        for (int j = MAXW-1; j >= 0; j--) {
            dp[cur][j] = dp[prev][j];
            if (j - w >= 0 && j - w < MAXW && dp[prev][j - w] != -1e18) dp[cur][j] = max(dp[cur][j], dp[prev][j - w] + v);
        }
    }
    ll ans = 0;
    for (int i = 0; i < MAXW; i++) ans = max(ans, dp[n%2][i]);//cout << x << " "; cout << endl;
    cout << ans << endl;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    //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