제출 #989184

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989184		parlimoos	Cloud Computing (CEOI18_clo)	C++14	100 / 100	569 ms	4124 KiB

clo

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define arr(x) array<ll , x>
#define endl '\n'
#define cl clear
#define bg begin

int n , m , sum;
vector<arr(3)> a , b;
vector<int> ord;
ll dp[2][1000001] , o;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0 ; i < n ; i++){
        int c , f , v;
        cin >> c >> f >> v;
        a.pb({c , f , v}) , b.pb({c , f , v}) , sum += c , o -= (1ll * v);
        for(int i = 0 ; i < c ; i++) ord.pb(f);
    }
    cin >> m;
    for(int i = 0 ; i < m ; i++){
        int c , f , v;
        cin >> c >> f >> v;
        a.pb({c , f , v});
    }
    sort(a.bg() , a.end() , [](arr(3) a , arr(3) b){
        return (a[1] < b[1]);
    });
    sort(ord.bg() , ord.end());
    for(int i = n + m - 1 ; i >= 0 ; i--){
        int di1 = (i & 1) , di2 = ((i + 1) & 1);
        for(int j = sum ; j >= 0 ; j--){
            dp[di1][j] = max(dp[di2][j] , dp[di1][j + 1]);
            if(j + a[i][0] <= sum and a[i][1] <= ord[j]) dp[di1][j] = max(dp[di1][j] , a[i][2] + dp[di2][j + a[i][0]]);
        }
    }
    cout << dp[0][0] + o;
}

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