제출 #555374

#제출 시각아이디문제언어결과실행 시간메모리
555374status_codingCloud Computing (CEOI18_clo)C++14
36 / 100
151 ms262144 KiB
#include <bits/stdc++.h> using namespace std; struct pos { long long nr, val, cost; pos(){} pos(long long nr, long long val, long long cost) { this->nr = nr; this->val = val; this->cost = cost; } bool operator<(pos b) const { return val < b.val; } }; long long n,m,ans; pos v[2005]; vector<pos> q[2005]; long long prof[100055]; long long dp[2005][100055]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>> v[i].nr >> v[i].val >> v[i].cost; sort(v+1, v+n+1); cin>>m; for(int i=1; i<=m; i++) { int nr, val, cost; cin>>nr>>val>>cost; for(int j=1; j<=n; j++) if(v[j].val >= val) { q[j].push_back(pos(nr, val, cost)); break; } } for(int i=1; i<=n+1; i++) for(int nr=0; nr<= 50 * n; nr++) dp[i][nr] = -1e18; dp[n+1][0] = 0; for(int i=n; i>=1; i--) { int sum = 0; for(auto it : q[i]) sum += it.nr; for(int j=0; j<= sum; j++) prof[j] = 0; for(auto it : q[i]) for(int j=sum; j>=it.nr; j--) prof[j] = max(prof[j], prof[j - it.nr] + it.cost); for(int last=0; last <= 50*n; last++) { if(dp[i+1][last] == -1e18) continue; for(int cur=0; cur<=sum; cur++) { if(last - cur >= 0) dp[i][last - cur] = max(dp[i][last - cur], dp[i+1][last] + prof[cur]); if(last + v[i].nr - cur >= 0 && last + v[i].nr - cur <= 1e5) dp[i][last + v[i].nr - cur] = max(dp[i][last + v[i].nr - cur], dp[i+1][last] + prof[cur] - v[i].cost); } } } for(int nr=0; nr<= 50*n; nr++) ans = max(ans, dp[1][nr]); 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...