제출 #1294508

#제출 시각아이디문제언어결과실행 시간메모리
1294508nathlol2Cloud Computing (CEOI18_clo)C++20
18 / 100
560 ms3676 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e3 + 5, W = 1e5 + 5, INF = 4e18;
int n, m, c[N], f[N], C[N], F[N], v[N], V[N];
vector<int> dp(W, INF), t(W, INF), dp1(W, -INF), t1(W, -INF);
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for(int i = 1;i<=n;i++) cin >> c[i] >> f[i] >> v[i];
    cin >> m;
    for(int i = 1;i<=m; i++) cin >> C[i] >> F[i] >> V[i];
    t[0] = 0;
    for(int i = 1;i<=n;i++){
        for(int j = 100000;j>=c[i];j--){
            if(t[j - c[i]] != INF){
                dp[j] = min(t[j], t[j - c[i]] + v[i]);
            }else{
                dp[j] = t[j];
            }
        }
        for(int j = 0;j <= 100000; j++) t[j] = min(t[j], dp[j]), dp[j] = INF;
    }
    dp[100000] = t[100000];
    for(int j = 99999;j>=0;j--){
        dp[j] = min(t[j], dp[j + 1]);
    }
    t1[0] = 0;
    for(int i = 1;i<=m;i++){
        for(int j = 100000;j>=C[i];j--){
            if(t1[j - C[i]] != -INF){
                dp1[j] = max(t1[j], t1[j - C[i]] + V[i]);
            }else{
                dp1[j] = t1[j];
            }
        }
        for (int j = 0; j <= 100000; j++) t1[j] = max(t1[j], dp1[j]), dp1[j] = -INF;
    }
    dp1[0] = max(0LL, t1[0]);
    for(int j = 1;j<=100000;j++){
        dp1[j] = max(dp1[j - 1], t1[j]);
    }
    int ans = 0;
    for(int j = 0;j<=100000;j++){
        ans = max(ans, dp1[j] - dp[j]);
    }
    cout << ans;
}
#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...