제출 #532809

#제출 시각아이디문제언어결과실행 시간메모리
532809exopengCloud Computing (CEOI18_clo)C++14
100 / 100
1529 ms2036 KiB
#include <bits/stdc++.h> using namespace std; #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define mp make_pair #define pb push_back #define lb lower_bound #define ub upper_bound #define f first #define ll long long #define ld long double #define s second #define pii pair<int,int> #define pdd pair<double,double> #define pll pair<ll,ll> #define is insert const long long INF = 1e18; const long long MOD = 1e9+7; const int MAXN = 2001; //store test cases here /* 4 4 2200 700 2 1800 10 20 2550 9999 4 2000 750 3 1 1500 300 6 1900 1500 3 2400 4550 */ int n,m; //clock rate, # of cores, and price pair<int,pii> co[MAXN]; pair<int,pii> od[MAXN]; ll dp[2][2001][51]; int main() { ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=0;i<2;i++){ for(int j=0;j<2001;j++){ for(int k=1;k<51;k++){ dp[i][j][k]=-1*INF; } } } for(int i=0;i<n;i++){ cin>>co[i].f>>co[i].s.f>>co[i].s.s; swap(co[i].f,co[i].s.f); } cin>>m; for(int i=0;i<m;i++){ cin>>od[i].f>>od[i].s.f>>od[i].s.s; swap(od[i].f,od[i].s.f); } sort(co,co+n,greater<pair<int,pii>>()); sort(od,od+m,greater<pair<int,pii>>()); ll mx=0; for(int i=0;i<=n;i++){ int ix=i%2; int nx=(ix+1)%2; for(int j=0;j<=m;j++){ for(int k=0;k<=50;k++){ if(j){ dp[ix][j][k]=max(dp[ix][j][k],dp[ix][j-1][k]); } mx=max(mx,dp[ix][j][k]); if(j==m||dp[ix][j][k]==-1*INF){ continue; } if(k>=od[j].s.f){ dp[ix][j+1][k-od[j].s.f]= max(dp[ix][j+1][k-od[j].s.f],dp[ix][j][k]+od[j].s.s); }else if(i!=n){ if(co[i].f>=od[j].f){ if(co[i].s.f+k>=od[j].s.f){ dp[nx][j+1][co[i].s.f+k-od[j].s.f] =max(dp[nx][j+1][co[i].s.f+k-od[j].s.f], dp[ix][j][k]+od[j].s.s-co[i].s.s); }else{ //can still buy however dp[nx][j][co[i].s.f+k]=max(dp[nx][j][co[i].s.f+k], dp[ix][j][k]-co[i].s.s); } } } } } for(int j=0;j<=m;j++){ dp[nx][j][0]=max(dp[nx][j][0],dp[ix][j][0]); dp[ix][j][0]=0; for(int k=1;k<=50;k++){ dp[nx][j][k]=max(dp[nx][j][k],dp[ix][j][k]); dp[ix][j][k]=-1*INF; } } } cout<<mx<<'\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...