제출 #1182586

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182586		Newtonabc	Cloud Computing (CEOI18_clo)	C++20	100 / 100	1151 ms	4036 KiB

clo

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+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[2][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 j=0;j<=m;j++) for(int k=1;k<=mxc;k++) dp[0][j][k]=dp[1][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++){
        int now=i&1,pre=(i+1)&1;
        //cout<<"i=" <<i <<"\n";
        for(int j=0;j<=m;j++){
            for(int k=0;k<=mxc;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[now][j][k]=max(dp[now][j][k],dp[pre][j][k]);
                //from dp[i][j-1][k] (not accept order)
                if(j!=0) dp[now][j][k]=max(dp[now][j][k],dp[now][j-1][k]);
                //buy the computer noted that i clock rate should be greater than or equal j+1 clock rate
                if(j+1<=m && csp>=ord[j+1].first && k-camt>=0 && dp[pre][j][k-camt]!=LLONG_MIN){
                    dp[now][j][k]=max(dp[now][j][k],dp[pre][j][k-camt]-cmn);
                }
                //accept the order (come from i,j-1,k+amount)
                if(j && k+oamt<=mxc && dp[now][j-1][k+oamt]!=LLONG_MIN){
                    dp[now][j][k]=max(dp[now][j][k],dp[now][j-1][k+oamt]+omn);
                }
                ans=max(ans,dp[now][j][k]);
                // if(dp[i][j][k]==LLONG_MIN) cout<<"*";
                // else cout<<dp[i][j][k];
                // cout<<" ";
            }
            //cout<<"\n";
        }
    }
    cout<<ans;
}

• Subtask 1: 18 / 18
• Subtask 2: 18 / 18
• Subtask 3: 18 / 18
• Subtask 4: 18 / 18
• Subtask 5: 18 / 18
• Subtask 6: 10 / 10