제출 #977312

#제출 시각아이디문제언어결과실행 시간메모리
977312PieArmyCloud Computing (CEOI18_clo)C++17
0 / 100
1 ms348 KiB
typedef long long ll; ll pie(ll army){return (1ll<<army);} #include <bits/stdc++.h> #define fr first #define sc second #define pb push_back #define endl '\n' #define mid ((left+right)>>1) const ll inf=2000000000000000005; const int sonsuz=2000000005; using namespace std; ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;} int n,m; int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin>>n; int c[n],f[n],v[n],C[m],F[m],V[m]; for(int i=0;i<n;i++){ cin>>c[i]>>f[i]>>v[i]; } cin>>m; for(int i=0;i<m;i++){ cin>>C[i]>>F[i]>>V[i]; } int p[n],P[m]; iota(p,p+n,0);iota(P,P+m,0); sort(p,p+n,[&](const int &x,const int &y){return f[x]>f[y];}); sort(P,P+m,[&](const int &x,const int &y){return F[x]>F[y];}); ll dp[n+1][51]; for(int i=0;i<=n;i++){ for(int j=0;j<=50;j++){ dp[i][j]=-inf; } } dp[0][0]=0; for(int i=0;i<m;i++){ ll dp2[n+1][51]; for(int j=0;j<=n;j++){ for(int l=0;l<=50;l++){ dp2[j][l]=-inf; } } for(int j=0;j<=n;j++){ for(int l=0;l<=50;l++){ if(dp[j][l]==-inf)continue; dp2[j][l]=max(dp2[j][l],dp[j][l]); if(l>=C[P[i]]){ dp2[j][l-C[P[i]]]=max(dp2[j][l-C[P[i]]],dp[j][l]+V[P[i]]); } if(j==n)continue; dp[j+1][l]=max(dp[j+1][l],dp[j][l]); if(f[p[j]]>=F[P[i]]){ if(l+c[p[j]]<C[P[i]]){ dp[j+1][l+c[p[j]]]=max(dp[j+1][l+c[p[j]]],dp[j][l]-v[p[j]]); } else if(l<C[P[i]]){ dp2[j+1][l+c[p[j]]-C[P[i]]]=max(dp2[j+1][l+c[p[j]]-C[P[i]]],dp[j][l]+V[P[i]]-v[p[j]]); } } } } for(int j=0;j<=n;j++){ for(int l=0;l<=50;l++){ dp[j][l]=dp2[j][l]; } } } ll ans=0; for(int i=0;i<=n;i++){ for(int j=0;j<=50;j++){ ans=max(ans,dp[i][j]); } } 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...