제출 #472979

#제출 시각아이디문제언어결과실행 시간메모리
472979fadi57Cloud Computing (CEOI18_clo)C++17
100 / 100
931 ms2060 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; const int mx=2009; typedef long long ll; int mod=1e9+7; const int MXm=22; #define F first #define S second const ll inf=1e14+10; int n,m; struct computer{ ll c,f,v,typ; }; ll dp[2000*50+90][2];computer a[mx+mx]; bool cmp(computer x,computer y){ if(x.f!=y.f){ return x.f>y.f; }else{ return x.typ<y.typ; }} int main(){ cin>>n; ll sum=0; for(int i=0;i<n;i++){ cin>>a[i].c>>a[i].f>>a[i].v; sum+=a[i].c; a[i].typ=0; } cin>>m; for(int i=n;i<m+n;i++){ cin>>a[i].c>>a[i].f>>a[i].v; a[i].typ=1; } sort(a,a+(n+m),cmp); for(int i=0;i<=sum;i++){ dp[i][1]=-inf; } dp[0][1]=0; ll ans=0; for(int i=0;i<n+m;i++){ for(int j=0;j<=sum;j++){ dp[j][i&1]=dp[j][(i+1)&1]; if(a[i].typ==0){ if(j-a[i].c>=0){ dp[j][i&1]=max(dp[j-a[i].c][(i+1)&1]-a[i].v,dp[j][i&1]); } }else{ if(a[i].c+j<=sum){ dp[j][i&1]=max(dp[j+a[i].c][(i+1)&1]+a[i].v,dp[j][i&1]); } } ans=max(ans,dp[j][i&1]); } } cout<<ans; }
#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...