Submission #796214

#TimeUsernameProblemLanguageResultExecution timeMemory
796214Dan4LifeTwo Dishes (JOI19_dishes)C++17
15 / 100
137 ms47668 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int mxN = (int)1e6+10; const int LINF = (int)2e18; int n, m; int a[2][mxN], s[2][mxN], p[2][mxN], pr[2][mxN], pr2[2][mxN]; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; int ans = -LINF; for(int j : {0,1}){ for(int i = 1; i <= n; i++){ cin >> a[j][i] >> s[j][i] >> p[j][i]; pr[j][i]=pr[j][i-1]+a[j][i]; pr2[j][i]=pr2[j][i-1]+p[j][i]; } swap(n,m); } if(max(n,m)<=3000){ int dp[2010][2010]; for(int i = 0; i <= n; i++) for(int j = 0; j <= m; j++) dp[i][j] = !!(i|j)*-LINF; for(int i = 0; i <= n; i++){ for(int j = 0; j <= m; j++){ int tim = pr[0][i]+pr[1][j]; if(i) dp[i][j] = max(dp[i][j],dp[i-1][j]+(tim<=s[0][i])*p[0][i]); if(j) dp[i][j] = max(dp[i][j],dp[i][j-1]+(tim<=s[1][j])*p[1][j]); } } cout << dp[n][m] << "\n"; return 0; } for(int j : {0,1}){ for(int i = 0; i <= n; i++){ if(pr[j][i]>s[j][1]) break; int l = 0, r = m; while(l<r){ int mid = (l+r+1)/2; if(pr[j^1][mid]+pr[j][i]<=s[j][1])l=mid; else r=mid-1; } ans = max(ans, pr2[j][i]+pr2[j^1][l]); } swap(n,m); } 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...