제출 #317431

#제출 시각아이디문제언어결과실행 시간메모리
317431HeheheCloud Computing (CEOI18_clo)C++14
100 / 100
466 ms1400 KiB
#include<bits/stdc++.h> //:3 using namespace std; typedef long long LL; #define all(a) (a).begin(), (a).end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int, int> #define sz(x) (int)((x).size()) #define int long long const int dx[] = {0, 1, 0, -1}; const int dy[] = {1, 0, -1, 0}; const LL inf = 2e6; const LL mod = 1e9 + 7; const int N = 2e6 + 11; const LL INF64 = 3e18 + 1; const double eps = 1e-14; const double PI = acos(-1); LL n, m, dp[N]; struct yes{ int c, f, cost, tip; }; yes a[N]; void solve(){ cin >> n; int sum = 0; for(int i = 1; i <= n; i++){ cin >> a[i].c >> a[i].f >> a[i].cost; a[i].tip = 0; sum += a[i].c; } cin >> m; for(int i = n + 1; i <= n + m; i++){ cin >> a[i].c >> a[i].f >> a[i].cost; a[i].tip = 1; } n += m; for(int i = 1; i <= sum; i++){ dp[i] = -INF64; } sort(a + 1, a + n + 1, [](yes l, yes r){ if(l.f == r.f)return (l.tip < r.tip); return (l.f > r.f); }); for(int i = 1; i <= n; i++){ int c = a[i].c, cost = a[i].cost, tip = a[i].tip; if(!tip){ for(int j = sum - c; j >= 0; j--){ if(dp[j] != -INF64)dp[j + c] = max(dp[j + c], dp[j] - cost); } }else{ for(int j = 0; j <= sum - c; j++){ if(dp[j + c] != -INF64)dp[j] = max(dp[j], dp[j + c] + cost); } } } int ans = 0; for(int i = 0; i <= sum; i++)ans = max(ans, dp[i]); cout << ans << '\n'; } int32_t main(){ ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); //cout << setprecision(6) << fixed; int T = 1; //cin >> T; while(T--){ solve(); } }
#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...