제출 #944467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944467		Captain_Georgia	Cloud Computing (CEOI18_clo)	C++17	100 / 100	386 ms	1704 KiB

clo

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

#define file \
            freopen("in.txt" , "r" , stdin); \
            freopen("out.txt" , "w" , stdout);

#define int long long

void test_case () {
    int n , m;
    cin >> n;
    int f[n] , c[n] , w[n];
    int sum = 0;
    for (int i = 0;i < n;i ++) {
        cin >> c[i] >> f[i] >> w[i];
    }
    cin >> m;
    int f_[m] , c_[m] , w_[m];
    set<int> s;
    s.insert(0);
    for (int i = 0;i < m;i ++) {
        cin >> c_[i] >> f_[i] >> w_[i];
        sum += c_[i];
        s.insert(f_[i]);
    }
    // cout << s.size() << "\n";
    vector<int> v(s.begin() , s.end());
    vector<pair<int , int>> g[m + 5] , g_[m + 5];
    for (int i = 0;i < n;i ++) {
        f[i] = lower_bound(v.begin() , v.end() , (int) *(-- s.upper_bound(f[i]))) - v.begin();
        // cout << f[i] << "  ";
        g[f[i]].push_back({c[i] , w[i]});
    }
    // cout << "\n";
    for (int i = 0;i < m;i ++) {
        // cout << f_[i] << "  ";
        f_[i] = lower_bound(v.begin() , v.end() , f_[i]) - v.begin();
        // cout << f_[i] << " || ";
        g_[f_[i]].push_back({c_[i] , w_[i]});
    }
    // cout << "\n";
    vector<int> dp(sum + 10 , 0);
    for (int i = 0;i <= m;i ++) {
        for (auto j : g_[i]) {
            for (int k = sum;k >= j.first;k --) {
                dp[k] = max(dp[k] , dp[k - j.first] +  j.second);
            }
        }
        for (auto j : g[i]) {
            for (int k = 0;k <= sum;k ++) {
                dp[k] = max(dp[k] , dp[min(k + j.first , sum)] - j.second);
            }
        }
    }
    cout << dp[0] << "\n";
}

int32_t main () {

    // file
    int TIME = clock();

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

    while (t --) {
        test_case();
    }

    cerr << "\nTime elapsed: " << (clock() - TIME) * 1000.0 / CLOCKS_PER_SEC << " ms\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