제출 #1261438

#제출 시각아이디문제언어결과실행 시간메모리
1261438doqCloud Computing (CEOI18_clo)C++20
100 / 100
204 ms1096 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long

#define fo(i,a,b) for(int i = (a); i <= (b); i++)
#define fod(i,a,b) for(int i = (a); i >= (b); i--)
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define ll long long

const int N = 2e3 + 5;
const int inf = 1e15;

int n, m;
struct pp {
    int fi, se, th;
} b[N * 2];
int nn;


bool cmp(pp a, pp b) {
    if(a.se != b.se) return a.se > b.se;
    return a.th < b.th;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

   // freopen("1.inp", "r", stdin);
   // freopen("1.out", "w", stdout);

    cin >> n;
    fo(i, 1, n){
        int x, y, w; cin >> x >> y >> w;
        b[i] = {x, y, -w};
    }

    cin >> m;
    nn = n + m;
    fo(i, 1, m) {
        int x, y, z; cin >> x >> y >> z;
        b[i + n] = {-x, y, z};
    }

    sort(b + 1, b + nn + 1, cmp);
    const int up = 2000 * 50;
    vector<int> f(up + 5, -inf);

    f[0] = 0;
    int sum = 0;
    fo(i, 1, nn) {
        if(b[i].fi > 0) {
            fod(j, sum, 0) if(j + b[i].fi <= up)
                f[j + b[i].fi] = max(f[j + b[i].fi], f[j] + b[i].th);
            sum += b[i].fi;
        } else {
            int tmp = -b[i].fi;
            fo(j, tmp, sum) {
                int now = j - tmp;
                f[now] = max(f[now], f[j] + b[i].th);
            }
        }
    }

    int res = 0;
    fo(i, 0, sum) res = max(res, f[i]);
    cout << res;
}
#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...