제출 #1182567

#제출 시각아이디문제언어결과실행 시간메모리
1182567NewtonabcCloud Computing (CEOI18_clo)C++20
0 / 100
23 ms56904 KiB
#include<bits/stdc++.h>
using namespace std;
const int N=250+10;
//speed,amount,money
vector<pair<int,pair<int,long long>>> com,ord;
//com from 1 to i,ord from 1 to j,number of cores left
long long dp[N][N][110];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    pair<int,pair<int,long long>> mx={INT_MAX,{0,0}};
    com.push_back(mx),ord.push_back(mx);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        int num,cr;
        long long p;
        cin>>num >>cr >>p;
        com.push_back({cr,{num,p}});
    }
    int m;
    cin>>m;
    for(int i=1;i<=m;i++){
        int num,cr;
        long long val;
        cin>>num >>cr >>val;
        ord.push_back({cr,{num,val}});
    }
    int mxc=105;
    for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=1;k<=mxc;k++) dp[i][j][k]=LLONG_MIN;
    //dp[i][j][0]=0
    sort(com.begin(),com.end(),greater<pair<int,pair<int,long long>>>());
    sort(ord.begin(),ord.end(),greater<pair<int,pair<int,long long>>>());
    long long ans=0;
    if(com[1].first>=ord[1].first) dp[1][0][com[1].second.first]=-com[1].second.second;
    for(int i=1;i<=n;i++){
        //cout<<"i=" <<i <<"\n";
        for(int j=1;j<=m;j++){
            for(int k=0;k<=20;k++){
                //com
                int csp=com[i].first,camt=com[i].second.first,osp=ord[j].first,oamt=ord[j].second.first;
                long long cmn=com[i].second.second,omn=ord[j].second.second;
                //from dp[i-1][j][k] (not buy computer)
                dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k]);
                //from dp[i][j-1][k] (not accept order)
                dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k]);
                //buy the computer noted that i clock rate should be greater than j clock rate
                if(j+1<=m && csp>=ord[j+1].first && k-camt>=0 && dp[i-1][j][k-camt]!=LLONG_MIN){
                    dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-camt]-cmn);
                }
                //accept the order (come from i,j-1,k+amount)
                if(k+oamt<=mxc && k+oamt<=mxc && dp[i][j-1][k+oamt]!=LLONG_MIN){
                    dp[i][j][k]=max(dp[i][j][k],dp[i][j-1][k+oamt]+omn);
                }
                ans=max(ans,dp[i][j][k]);
                // if(dp[i][j][k]==LLONG_MIN) cout<<"*";
                // else cout<<dp[i][j][k];
                // cout<<" ";
            }
            //cout<<"\n";
        }
    }
    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...