Submission #1194927

#TimeUsernameProblemLanguageResultExecution timeMemory
1194927euclidCloud Computing (CEOI18_clo)C++20
100 / 100
669 ms2192 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define fi first #define se second #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define vl vector<ll> int n, m; const int MN = 2003, MC = 53; const ll INF = 1e15 + 7; ll dp[2][MC*MN]; struct transaction { ll c, f, v; bool operator<(transaction t) const { if(f == t.f) return v < t.v; return f > t.f; } } a[2*MN]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i].c >> a[i].f >> a[i].v, a[i].v *= -1; cin >> m; for(int i = n+1; i <= n+m; i++) cin >> a[i].c >> a[i].f >> a[i].v; sort(a+1, a+1+n+m); for(int i = 0; i < 2; i++) for(int j = 0; j < n*MC; j++) dp[i][j] = -INF; dp[0][0] = 0; ll ans = 0; for(int i = 1; i <= m+n; i++) { // if(i != 1 && a[i].f == a[i-1].f) assert(a[i].v > a[i-1].v); // else if(i != 1) assert(a[i].f < a[i-1].f); for(int j = 0; j < n*MC; j++) { dp[1][j] = dp[0][j]; if(a[i].v < 0) { if(j-a[i].c >= 0) dp[1][j] = max(dp[1][j], dp[0][j-a[i].c]+a[i].v); } else { if(j+a[i].c < n*MC) dp[1][j] = max(dp[1][j], dp[0][j+a[i].c]+a[i].v); } if(i == m+n) ans = max(ans, dp[1][j]); } for(int j = 0; j < n*MC; j++) dp[0][j] = dp[1][j]; } cout << ans << '\n'; }
#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...