제출 #77934

#제출 시각아이디문제언어결과실행 시간메모리
77934SaboonCloud Computing (CEOI18_clo)C++14
18 / 100
384 ms3168 KiB
#include <iostream>
#include <queue>
#include <bitset>
#include <stack>
#include <vector>
#include <cstring>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <iomanip>
#define F first
#define S second
#define PB push_back
#define PF push_front
#define MP make_pair

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int inf = 1e9 + 100;
const int maxn = 2e5 + 100;

int n, m;

ll c[maxn], f[maxn], v[maxn], C[maxn], F[maxn], V[maxn];

ll dp[maxn], di[maxn];
void solve_just_for_f () {
    memset (dp, 63, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = n * 50; j >= c[i]; j--) {
            dp[j] = min (dp[j], dp[j - c[i]] + v[i]);
        }
    }
    for (int i = n - 1; i >= 0; i--)
        dp[i] = min (dp[i], dp[i + 1]);

    di[0] = 0;
    for (int i = 0; i < m; i++) {
        for (int j = n * 50; j >= C[i]; j--) {
            di[j] = max (di[j], di[j - C[i]] + V[i]);
        }
    }
    ll ans = 0;
    for (int i = 0; i <= 50 * n; i++)
        ans = max (ans, di[i] - dp[i]);
    cout << ans << endl;
    exit (0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> c[i] >> f[i] >> v[i];
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> C[i] >> F[i] >> V[i];
    solve_just_for_f ();
}
#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...