제출 #1268419

#제출 시각아이디문제언어결과실행 시간메모리
1268419dhuyyyyCloud Computing (CEOI18_clo)C++20
54 / 100
123 ms1348 KiB
#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,3>;

const int N = 1e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;

int n, m, S, ans = 0, dp[N];

aa a[N];
bool cmp(aa a, aa b){
    return a[1] > b[1];
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= 2; j++){
            cin >> a[i][j];
        }
        S += a[i][0];
        a[i][2] *= -1;
    }
    cin >> m;
    for (int i = 1; i <= m; i++){
        for (int j = 0; j <= 2; j++){
            cin >> a[i+n][j];
        }
        S += a[i+n][0];
        a[i+n][0] *= -1;
    }
    n += m;
    sort(a+1,a+1+n,cmp);
    for (int i = 1; i <= S; i++) dp[i] = -1e18;
    for (int i = 1; i <= n; i++){
        if (a[i][0] > 0){
            for (int j = S; j >= a[i][0]; j--){
                dp[j] = max(dp[j],dp[j - a[i][0]] + a[i][2]);
            }
        } else{
            for (int j = 0; j <= S + a[i][0]; j++){
                dp[j] = max(dp[j],dp[j - a[i][0]] + a[i][2]);
            }
        }
    }
    for (int i = 0; i <= S; i++){
         ans = max(ans,dp[i]);
    }
    cout << ans;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...