제출 #963624

#제출 시각아이디문제언어결과실행 시간메모리
963624oblantisCloud Computing (CEOI18_clo)C++17
100 / 100
369 ms1368 KiB
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define ss second
#define ff first
#define vt vector
#define uid(a, b) uniform_int_distribution<int>(a, b)(mt)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll inf = 1e18;
const int mod = 1e9+7;
const int maxn = 100000 + 5;
mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
ll dp[maxn];
void solve() {
    int n, m;
    cin >> n;
    dp[0] = 0;
    for(int i = 1; i < maxn; i++)dp[i] = -inf;
    tuple<int, bool, int, int> e[4000];
    for(int i = 0, c, f, v; i < n; i++){
        cin >> c >> f >> v;
        e[i] = make_tuple(f, 1, c, v);
    }
    cin >> m;
    for(int i = 0, c, f, v; i < m; i++){
        cin >> c >> f >> v;
        e[i + n] = make_tuple(f, 0, c, v);
    }
    sort(e, e + n + m);
    reverse(e, e + n + m);
    for(int i = 0; i < n + m; i++){
        auto [f, wt, c, v] = e[i];
        if(wt == 0){
            for(int j = 0; j + c < maxn; j++){
                dp[j] = max(dp[j], dp[j + c] + v);
            }
        }
        else {
            for(int j = maxn - 1; j >= c; j--){
                dp[j] = max(dp[j], dp[j - c] - v);
            }
        }
    }
    cout << *max_element(dp, dp + maxn);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int times = 1; //cin >> times;
	for(int i = 1; i <= times; i++) {
		solve();
	}
	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...