제출 #1273808

#제출 시각아이디문제언어결과실행 시간메모리
1273808mahersefoCloud Computing (CEOI18_clo)C++17
100 / 100
581 ms2072 KiB
#include<bits/stdc++.h>
#define ll long long
#define all(a) (a).begin() , (a).end()
#define endl '\n'
using namespace std;
void readFromFile(string input = "input.txt",string output="output.txt") {

}
const int N = 2e3+1;
#define ty array<int,4>
ty a[2*N];
int n,m,t;
ll dp[2][50*N];
void solve() {
    cin >> n;
    for(int i = 0 ; i < n ; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        a[i][3] = 1;
    }
    cin >> m;
    for(int i = n ; i < m+n ; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2];
        a[i][3] = 0;
    }
    t = n+m;
    sort(a,a+t,[&](ty x,ty y) {
        if(x[1] != y[1]) return x[1] < y[1];
        return x[3] < y[3];
    });
    int sum = 0;
    for(int i = 0 ; i < t ; i++) {
        if(a[i][3] == 0) sum += a[i][0];
    }
    for(int i = 1 ; i <= sum ; i++) dp[0][i] = -1e18;
    dp[0][0] = 0;
    for(int i = t-1 ; i >= 0 ; i--) {
        for(int j = 0 ;j <= sum ; j++) {
            dp[1][j] = dp[0][j];
            if(a[i][3] && j) {
                dp[1][j] = max(dp[1][j] , dp[0][max(0 , j-a[i][0])] - a[i][2]);
            }
            if(!a[i][3] && j+a[i][0] <= sum) {
                dp[1][j] = max(dp[1][j] , dp[0][j+a[i][0]] + a[i][2]);
            }
        }
        for(int j = 0 ; j <= sum ; j++) dp[0][j] = dp[1][j];
    }
    cout << dp[0][0] << endl;
}
int32_t main() {
    readFromFile();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
//    cin >> t;
    for(int i = 0 ; i < t ; i++) {
        solve();
    }
}
#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...