This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define per(i, a, b) for (int i = b - 1; i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
const int INF = 1000000007;
struct str {
ll val = -1e14;
};
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n, m;
vector<pair<ii, pair<ll, int>>> dpvec;
vector<iii> samevvec;
ll c, f, v, sumc = 0, ans = 0;
bool samev = 1;
cin >> n;
rep(i, 0, n) {
cin >> c >> f >> v;
if (v != 1) samev = 0;
dpvec.push_back({{f, 1}, {v, c}});
samevvec.push_back({f, {1, c}});
}
cin >> m;
rep(i, 0, m) {
cin >> c >> f >> v;
sumc += c;
dpvec.push_back({{f, 0}, {v, c}});
samevvec.push_back({f, {0, c}});
}
if (!samev) {
sort(all(dpvec), greater<>());
umap<int, str> dp, dp2;
dp[0].val = 0;
trav(item, dpvec) {
int query;
tie(f, query) = item.first;
tie(v, c) = item.second;
trav(val, dp) {
int cores = val.first;
ll cost = val.second.val;
dp2[cores].val = max(dp2[cores].val, cost);
if (query && cores < sumc)
dp2[cores + c].val = max(dp2[cores + c].val, cost - v);
else if (!query && c <= cores)
dp2[cores - c].val = max(dp2[cores - c].val, cost + v);
}
dp.swap(dp2);
dp2.clear();
}
trav(val, dp) ans = max(ans, val.second.val);
}
else {
cout << endl;
sort(all(samevvec), greater<>());
}
cout << ans << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |