Submission #1261367

#TimeUsernameProblemLanguageResultExecution timeMemory
1261367dhuyyyyCloud Computing (CEOI18_clo)C++20
100 / 100
182 ms2132 KiB
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; using ll = long long; using ii = pair<int,int>; using pii = pair<int,ii>; using aa = array<int,4>; const int N = 2e5+5; const int INF = 1e9; const int MOD = 998244353; int n,m,ans = 0,dp[N]; aa a[N*2+5]; bool cmp(aa a,aa b){ return (a[1] != b[1] ? a[1] > b[1] : a[3] < b[3]); } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n; for (int i = 1; i <= n; i++){ for (int j = 0; j <= 2; j++) cin >> a[i][j]; } cin >> m; for (int i = n+1; i <= n+m; i++){ for (int j = 0; j <= 2; j++) cin >> a[i][j]; a[i][3] = 1; } sort(a+1,a+1+n+m,cmp); int cur = 0; for (int i = 1; i <= N-5; i++) dp[i] = -1e18; for (int i = 1; i <= n+m; i++){ if (!a[i][3]){ for (int j = cur; j >= 0; j--){ dp[j+a[i][0]] = max(dp[j+a[i][0]],dp[j] - a[i][2]); } cur += a[i][0]; } else{ for (int j = a[i][0]; j <= cur; j++){ dp[j-a[i][0]] = max(dp[j-a[i][0]],dp[j] + a[i][2]); } } } for (int i = 0; i <= N-5; i++) ans = max(ans,dp[i]); cout << ans; 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...