제출 #1094956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1094956		SoMotThanhXuan	Cloud Computing (CEOI18_clo)	C++17	100 / 100	552 ms	2140 KiB

clo

#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e3 + 5;
int N, M;
struct xx{
    int C, F, V;
    bool operator < (const xx &rhs) const{
        return F !=rhs.F ? F > rhs.F : C > rhs.C;
    }
}comp[maxN * 2];
const long long INFLL = 1e18;
long long dp[2][50 * 2000 + 1];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N;
    int sumC  = 0;
    for(int i = 1; i <= N; ++i){
        cin >> comp[i].C >> comp[i].F >> comp[i].V;
        comp[i].V = - comp[i].V;
        sumC += comp[i].C;
    }
    cin >> M;
    for(int i = N + 1; i <= N + M; ++i){
        cin >> comp[i].C >> comp[i].F >> comp[i].V;
        comp[i].C = - comp[i].C;
    }
    int K = N + M;
    sort(comp + 1, comp + 1 + K);
    int cur = 0, pre = 1;
    for(int st = 0; st <= 1; ++st)for(int curC = 0; curC <= sumC; ++curC){
        dp[st][curC] = -INFLL;
    }
    dp[0][0] = 0;
    for(int i = 1; i <= K; ++i){
        cur ^= 1;
        pre ^= 1;
        for(int curC = 0; curC <= sumC; ++curC)dp[cur][curC] = dp[pre][curC];
        for(int curC = 0; curC <= sumC; ++curC){
            if(curC + comp[i].C >= 0 && curC + comp[i].C <= sumC){
                dp[cur][curC + comp[i].C] = max(dp[cur][curC + comp[i].C], dp[pre][curC] + comp[i].V);
            }
        }
    }
    long long res = 0;
    for(int curC = 0; curC <= sumC; ++curC) res = max(res, dp[cur][curC]);
    cout << res;
    return 0;
}

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