제출 #848434

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
848434		LOLOLO	Cloud Computing (CEOI18_clo)	C++17	100 / 100	547 ms	3164 KiB

clo

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e4 + 10;

bool cmp(vector <ll> a, vector <ll> b) {
    if (a[1] == b[1]) {
        return a[3] > b[3]; 
    }

    return a[1] > b[1];
}

void maximize(ll &a, ll b) {
    if (a < b)
        a = b;
}

ll solve() {
    int n;
    cin >> n;
    vector < vector <ll>> a(n);
    for (auto &x : a) {
        x.resize(4);
        cin >> x[0] >> x[1] >> x[2];
        x[3] = 1;
    }

    int m;
    cin >> m;

    vector < vector <ll>> b(m);
    for (auto &x : b) {
        x.resize(4);
        cin >> x[0] >> x[1] >> x[2];
        x[3] = -1;
    }

    for (auto x : b)
        a.pb(x);

    sort(all(a), cmp);

    vector < vector <ll>> dp(2, vector <ll> (n * 50 + 10, -1e16));
    dp[0][0] = 0;
    ll ans = 0;

    for (int i = 1; i <= n + m; i++) {
        int t = (i % 2);
        for (int j = 0; j <= n * 50; j++) {
            dp[t][j] = dp[1 - t][j];
            if (a[i - 1][3] == 1) {
                if (j >= a[i - 1][0]) {
                    maximize(dp[t][j], dp[1 - t][j - a[i - 1][0]] - a[i - 1][2]);
                }
            } else {
                if (a[i - 1][0] + j <= n * 50) {
                    maximize(dp[t][j], dp[1 - t][j + a[i - 1][0]] + a[i - 1][2]);
                }
            }
            maximize(ans, dp[t][j]);
        }
    }

    return ans;
}

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL);

    int t = 1;
    //cin >> t;

    while (t--) {
        //solve();
        cout << solve() << "\n";
    }

    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