제출 #1303526

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1303526		tredsused70	Cloud Computing (CEOI18_clo)	C++20	100 / 100	268 ms	1268 KiB

clo

//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC optimize("trapv")
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define mpr make_pair
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int nmax = 2011, mod = 1000000007, inf = 2000010000, key = 200003, lg = 20, block = 300;
const ll infll = 4000000000000000000;
const ld eps = 1e-9;

const int cmax = 50;

ll dp[nmax * cmax];

void solve()
{
    int n, m;
    cin >> n;
    vector<array<int, 3>> computers(n + 1);
    for(int i = 0; i < n; i++)
        cin >> computers[i][1] >> computers[i][0] >> computers[i][2];
    cin >> m;
    vector<array<int, 3>> tasks(m);
    for(int i = 0; i < m; i++)
        cin >> tasks[i][1] >> tasks[i][0] >> tasks[i][2];
    computers[n] = {0, 0, 0};
    sort(all(computers));
    sort(all(tasks));
    int maxcores = cmax * n;
    fill(dp, dp + maxcores + 1, -infll / 2);
    dp[0] = 0;
    for(int i = n; i >= 1; i--) {
        int cur_freq = computers[i][0];
        int prev_freq = computers[i - 1][0];
        int cur_cores = computers[i][1];
        int cur_cost = computers[i][2];
        for(int j = maxcores; j >= cur_cores; j--)
            dp[j] = max(dp[j], dp[j - cur_cores] - cur_cost);
        //cout << "curdp\n";
        //for(int i1 = 0; i1 <= maxcores; i1++) {
            //cout << dp[i1] << "\n";
        //}
        //cout << "\n";
        for(int j = 0; j < m; j++) {
            if(tasks[j][0] <= cur_freq && tasks[j][0] > prev_freq) {
                //cout << "update tasks " << j << "\n";
                cur_cores = tasks[j][1];
                cur_cost = tasks[j][2];
                for(int cores = cur_cores; cores <= maxcores; cores++) {
                    dp[cores - cur_cores] = max(dp[cores - cur_cores], dp[cores] + cur_cost);
                }
                //cout << "curdp\n";
                //for(int i1 = 0; i1 <= maxcores; i1++) {
                    //cout << dp[i1] << "\n";
               // }
                //cout << "\n";
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i <= maxcores; i++) {
        //cout << dp[i] << "\n";
        ans = max(ans, dp[i]);
    }
    cout << ans << "\n";
    return ;
}

int main()
{
    //freopen("exercise.in","r",stdin);
    //freopen("exercise.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    srand(8713);
    //init();
    int t = 1;
    //cin >> t;
    //int t_ = t;
    //t = rdi();
    while(t--) {
        //cout << "Case #" << t_ - t << ": ";
        solve();
    }
    //flush();
    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