제출 #496601

#제출 시각아이디문제언어결과실행 시간메모리
496601DDTerziev04Cloud Computing (CEOI18_clo)C++14
36 / 100
1121 ms4044 KiB
#include<iostream> #include<tuple> #include<vector> #include<algorithm> using namespace std; const int MAXN=2000, MAXC=50; const long long INF=1e18; bool CompareTuples(tuple<int, int, int> a, tuple<int, int, int> b) { return get<1>(a)>get<1>(b); } tuple<int, int, int> p[2*MAXN]; long long dp[2][MAXN*MAXC+1]; bool usd[2][MAXN*MAXC+1]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i=0; i<n; i++) { int c, f, v; cin >> c >> f >> v; p[i]={c, f, -v}; } int m; cin >> m; for(int i=n; i<n+m; i++) { int c, f, v; cin >> c >> f >> v; p[i]={-c, f, v}; } sort(p, p+n+m, CompareTuples); for(int j=0; j<=n*MAXC; j++) { dp[0][j]=-INF, dp[1][j]=-INF; usd[0][j]=false, usd[1][j]=false; } dp[0][0]=0, usd[0][0]=true; long long ans=0; for(int i=0; i<n+m; i++) { for(int j=0; j<=n*MAXC; j++) { int c, f, v; tie(c, f, v)=p[i]; if(!usd[0][j]) { continue; } dp[1][j]=max(dp[1][j], dp[0][j]); dp[1][j+c]=max(dp[1][j+c], dp[0][j]+v); usd[1][j]=true; usd[1][j+c]=true; ans=max(ans, dp[0][j]); } for(int j=0; j<=n*MAXC; j++) { dp[0][j]=dp[1][j], dp[1][j]=-INF; usd[0][j]=usd[1][j], usd[1][j]=false; } } for(int i=0; i<=n*MAXC; i++) { ans=max(ans, dp[0][i]); } cout << ans << "\n"; 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...