Submission #1097522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097522		TrinhKhanhDung	Cloud Computing (CEOI18_clo)	C++14	100 / 100	331 ms	1368 KiB

clo

#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define sz(x) (int)x.size()
#define ALL(v) v.begin(),v.end()
#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
#define oo (ll)1e18
#define INF (ll)1e9
#define MOD (ll)(998244353)

using namespace std;

template<class T1, class T2>
    bool maximize(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

template<class T1, class T2>
    bool minimize(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}

template<class T1, class T2>
    void add(T1 &a, T2 b){a += b; if(a >= MOD) a -= MOD;}

template<class T1, class T2>
    void sub(T1 &a, T2 b){a -= b; if(a < 0) a += MOD;}

template<class T>
    void cps(T &v){sort(ALL(v)); v.resize(unique(ALL(v)) - v.begin());}

const int MAX = 2003, MAX_VAL = 1e5 + 10;

int N, M;
ll dp[MAX_VAL];
array<int, 3> pc[MAX], cus[MAX];

bool cmp(const array<int, 3> &a, const array<int, 3> &b){
    return a[1] < b[1];
}

void solve(){
    cin >> N;
    for(int i = 1; i <= N; i++){
        for(int j = 0; j < 3; j++) cin >> pc[i][j];
    }

    cin >> M;
    for(int i = 1; i <= M; i++){
        for(int j = 0; j < 3; j++) cin >> cus[i][j];
    }

    sort(pc + 1, pc + N + 1, cmp);
    sort(cus + 1, cus + M + 1, cmp);

    memset(dp, -0x3f, sizeof dp);
    dp[0] = 0;

    int cur = 0, j = N;
    for(int i = M; i >= 1; i--){
        while(j >= 1 && pc[j][1] >= cus[i][1]){
            for(int k = cur; k >= 0; k--){
                maximize(dp[k + pc[j][0]], dp[k] - pc[j][2]);
            }
            cur += pc[j][0];
            j--;
        }
        for(int k = 0; k <= cur - cus[i][0]; k++){
            maximize(dp[k], dp[k + cus[i][0]] + cus[i][2]);
        }
    }

    ll ans = 0;

    for(int i = 0; i <= cur; i++){
        maximize(ans, dp[i]);
    }

    cout << ans << '\n';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
//     freopen("cnt-mst.inp","r",stdin);
//     freopen("cnt-mst.out","w",stdout);

    int t = 1;
//    cin >> t;
    while(t--)
        solve();

    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