제출 #1329881

#제출 시각아이디문제언어결과실행 시간메모리
1329881newbie_tCloud Computing (CEOI18_clo)C++20
0 / 100
187 ms2036 KiB
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define m_p make_pair
#define str string
#define lowbit(x) (x & (-x))
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define siz(x) (int)x.size()
#define int long long
typedef pair<int, int> pi;
//typedef __int128 it;
const int Maxn = 4000 + 10;
const int Maxm = 1e5 + 10;
const int inf = 1e18;
const int mod = 998244353;
template<class T>
inline T add(T a, T b) { return ((a + b) > mod ? (a + b) - mod : (a + b)); }
template<class T>
inline T sub(T a, T b) { return (a > b ? a - b : (a - b + mod)); }
template<class T>
inline T mul(T a, T b) { return (T)(a * b % mod); }
struct Node {
    int c, f, v, idx;
} cnt[Maxn];
inline bool cmp (Node x, Node y) {
    return x.f > y.f;
}
int F[2][Maxm];
signed main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> cnt[i].c >> cnt[i].f >> cnt[i].v, cnt[i].idx = i;
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++) cin >> cnt[i + n].c >> cnt[i + n].f >> cnt[i + n].v, cnt[i + n].idx = i + n;
    sort (cnt + 1, cnt + n + m + 1, cmp);
    int I = 0;
    for (int i = 0; i < Maxm; i++) F[I ^ 1][i] = -inf;
    F[I ^ 1][0] = 0;
    bool ok = false;
    for (int i = 1; i <= n + m; i++) {
        for (int j = 1; j < Maxm; j++) F[I][j] = -inf;
        F[I ^ 1][0] = max(F[I ^ 1][0], 0ll);
        for (int j = 0; j < Maxm - cnt[i].c; j++) {
            if (cnt[i].idx <= n && j >= cnt[i].c) {
                F[I][j] = max(F[I ^ 1][j], F[I ^ 1][j - cnt[i].c] - cnt[i].v);
            }
            else if (cnt[i].idx > n) {
                F[I][j] = max(F[I ^ 1][j], F[I ^ 1][j + cnt[i].c] + cnt[i].v);
            }
            // cout << i << ' ' << j << ' ' <<F[I][j] << "\n";
        }
        I ^= 1;
    }
    I ^= 1;
    int ans = -inf;
    for (int i = 0; i < Maxm; i++) ans = max(ans, F[I][i]);
    cout << ans << "\n";
    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...