Submission #716095

#	Time	Username	Problem	Language	Result	Execution time	Memory
716095		nonono	Cloud Computing (CEOI18_clo)	C++17	100 / 100	254 ms	1256 KiB

clo

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

const int mxC = 50;
const long long inf = 1e18;
const int mxN = 2e3 + 10;

struct Data {
    int c, f, v;
    
    bool operator < (const Data &x) const {
        return f > x.f;
    }
};

int n, m, sumC = 0;
long long dp[mxN * mxC];
Data a[mxN], b[mxN];

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

void solve(int i){
    for(int j = sumC; j >= 0; j --){
        maximize(dp[j + a[i].c], dp[j] - a[i].v);
    }
}
    
void _solve(int i){
    for(int j = b[i].c; j <= sumC; j ++){
        maximize(dp[j - b[i].c], dp[j] + b[i].v);
    }
}

signed main(){
 ios_base::sync_with_stdio();  
 cin.tie(); cout.tie();
        
    cin >> n;
    
    for(int i = 1; i <= n; i ++){
        int c, f, v;
        cin >> c >> f >> v;
        
        a[i] = {c, f, v};
    }
    
    sort(a + 1, a + 1 + n);
    
    cin >> m;
    
    for(int i = 1; i <= m; i ++){
        int c, f, v;
        cin >> c >> f >> v;
        
        b[i] = {c, f, v};
    }
    
    sort(b + 1, b + 1 + m);
    
    for(int i = 0; i <= n * mxC; i ++){
        dp[i] = - inf;
    }
    
    dp[0] = 0;
    
    int _i = 0;
    while(_i + 1 <= m && b[_i + 1].f > a[1].f) _i ++ ;
        
    for(int i = 1, j = 1; i <= n; i = j + 1){
        for(j = i; j + 1 <= n && a[j + 1].f == a[i].f;) j ++ ;
        
        for(int k = i; k <= j; k ++){
            solve(k);
            sumC += a[k].c;
        }
        
        for(; _i + 1 <= m && b[_i + 1].f > a[j + 1].f;){
            _i ++ ;
            _solve(_i);
        }
        
        //cout << j << " " << _i << "\n";
    }
    
    long long ans = 0;
    for(int i = 0; i <= sumC; i ++){
        ans = max(ans, dp[i]);
        //cout << dp[i] << "\n";
    }
    
    cout << ans << "\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