Submission #949976

#	Time	Username	Problem	Language	Result	Execution time	Memory
949976		berr	Cloud Computing (CEOI18_clo)	C++17	100 / 100	458 ms	1372 KiB

clo

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


signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;

    vector<array<int, 3>> comp(n);
    
    for(auto &[c, f, v]: comp) cin >> c >> f >> v;

    sort(comp.begin(), comp.end(), [&](auto i, auto j){
        return i[1] > j[1];
    });

    vector<int> val(n*50+2, (int)-1e18);
    val[0] = 0;

    int m; cin >> m;

    vector<array<int, 3>> cust(m);

    for(auto &[c, f, v]: cust) cin >> c >> f >> v;

    sort(cust.begin(), cust.end(), [&](auto i, auto j){
        return i[1] > j[1];
    });

    int pos=0, s=val.size()-1;
    for(int i=0; i<m; i++){ 
        while(pos<n && comp[pos][1] >= cust[i][1]){
            for(int j=s; j>=0; j--){
                if(val[j]==(int)-1e18) continue;
                int v = j+comp[pos][0];
                
                val[v] = max(val[v], val[j] - comp[pos][2]);
            }
            pos++;
        }

        for(int j=cust[i][0]; j<=s; j++){
            val[j-cust[i][0]] = max(val[j-cust[i][0]], val[j]+cust[i][2]);
        }

    }

    int ans = 0;

    for(auto i: val) ans=max(ans, i);

    cout << ans;
}   

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