Submission #254308

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
254308	2020-07-29T20:12:36 Z	MarcoMeijer	Cloud Computing (CEOI18_clo)	C++14	100 / 100	2578 ms	2324 KB

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

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 2010;
ll n, m;
ll c[MX], f[MX], v[MX];
ll C[MX], F[MX], V[MX];
ll sa[MX], SA[MX];

vector<vector<vll>> dp;

ll DP(ll i, ll j, ll k) {
    if(i < 0) return 0;
    if(j < 0) return 0;
    if(k > 50) return -INF;
    return dp[i%2][j][k];
}

void program() {
    IN(n);
    RE(i,n) IN(c[i], f[i], v[i]);
    IN(m);
    RE(i,m) IN(C[i], F[i], V[i]);

    RE(i,n) sa[i]=i;
    sort(sa,sa+n,[](int i, int j) {
        return f[i]<f[j];
    });
    RE(i,m) SA[i]=i;
    sort(SA,SA+m,[](int i, int j) {
        return F[i]<F[j];
    });

    dp.resize(2);
    RE(i,2) {
        dp[i].resize(m+1);
        RE(j,m) dp[i][j].resize(51);
    }

    RE(i,n+1) RE(j,m) RE(k,51) {
        ll ans = DP(i,j-1,k); // dont give customer j her cores
        ans = max(ans,DP(i-1,j,k)); // dont buy computer i

        // give customer j her cores
        if(k >= C[SA[j]]) {
            ans = max(ans, DP(i,j-1,k-C[SA[j]]) + V[SA[j]]);
        }

        // buy computer i, and give customer j her cores
        if(i != 0 && f[sa[i-1]] >= F[SA[j]] && k+c[sa[i-1]] >= C[SA[j]]) {
            ans = max(ans, DP(i-1,j-1,k+c[sa[i-1]]-C[SA[j]]) - v[sa[i-1]] + V[SA[j]]);
        }

        // buy computer i
        if(i != 0 && f[sa[i-1]] >= F[SA[j]]) {
            ans = max(ans, DP(i-1,j,k+c[sa[i-1]])-v[sa[i-1]]);
        }

        dp[i%2][j][k] = ans;
    }

    OUTL(dp[n%2][m-1][0]);
}

Subtask #1
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	19 ms	2048 KB	Output is correct
6	Correct	29 ms	2048 KB	Output is correct
7	Correct	20 ms	2176 KB	Output is correct
8	Correct	19 ms	2176 KB	Output is correct

Subtask #2
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	7 ms	384 KB	Output is correct
6	Correct	8 ms	384 KB	Output is correct
7	Correct	14 ms	384 KB	Output is correct
8	Correct	20 ms	512 KB	Output is correct
9	Correct	18 ms	384 KB	Output is correct

Subtask #3
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct
4	Correct	8 ms	384 KB	Output is correct
5	Correct	28 ms	512 KB	Output is correct
6	Correct	29 ms	512 KB	Output is correct
7	Correct	42 ms	640 KB	Output is correct
8	Correct	43 ms	640 KB	Output is correct

Subtask #4
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	9 ms	384 KB	Output is correct
4	Correct	21 ms	1920 KB	Output is correct
5	Correct	2521 ms	2032 KB	Output is correct
6	Correct	2551 ms	2272 KB	Output is correct
7	Correct	2578 ms	2296 KB	Output is correct
8	Correct	2444 ms	2300 KB	Output is correct

Subtask #5
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	90 ms	640 KB	Output is correct
4	Correct	870 ms	1532 KB	Output is correct
5	Correct	2024 ms	2228 KB	Output is correct
6	Correct	2523 ms	2232 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	1 ms	512 KB	Output is correct
4	Correct	2 ms	512 KB	Output is correct
5	Correct	19 ms	2048 KB	Output is correct
6	Correct	29 ms	2048 KB	Output is correct
7	Correct	20 ms	2176 KB	Output is correct
8	Correct	19 ms	2176 KB	Output is correct
9	Correct	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	7 ms	384 KB	Output is correct
14	Correct	8 ms	384 KB	Output is correct
15	Correct	14 ms	384 KB	Output is correct
16	Correct	20 ms	512 KB	Output is correct
17	Correct	18 ms	384 KB	Output is correct
18	Correct	0 ms	384 KB	Output is correct
19	Correct	1 ms	384 KB	Output is correct
20	Correct	5 ms	512 KB	Output is correct
21	Correct	8 ms	384 KB	Output is correct
22	Correct	28 ms	512 KB	Output is correct
23	Correct	29 ms	512 KB	Output is correct
24	Correct	42 ms	640 KB	Output is correct
25	Correct	43 ms	640 KB	Output is correct
26	Correct	1 ms	384 KB	Output is correct
27	Correct	1 ms	384 KB	Output is correct
28	Correct	9 ms	384 KB	Output is correct
29	Correct	21 ms	1920 KB	Output is correct
30	Correct	2521 ms	2032 KB	Output is correct
31	Correct	2551 ms	2272 KB	Output is correct
32	Correct	2578 ms	2296 KB	Output is correct
33	Correct	2444 ms	2300 KB	Output is correct
34	Correct	0 ms	384 KB	Output is correct
35	Correct	3 ms	384 KB	Output is correct
36	Correct	90 ms	640 KB	Output is correct
37	Correct	870 ms	1532 KB	Output is correct
38	Correct	2024 ms	2228 KB	Output is correct
39	Correct	2523 ms	2232 KB	Output is correct
40	Correct	150 ms	908 KB	Output is correct
41	Correct	457 ms	1528 KB	Output is correct
42	Correct	1564 ms	1840 KB	Output is correct
43	Correct	2358 ms	2296 KB	Output is correct
44	Correct	2357 ms	2296 KB	Output is correct
45	Correct	2033 ms	2324 KB	Output is correct
46	Correct	658 ms	1280 KB	Output is correct
47	Correct	1509 ms	1792 KB	Output is correct
48	Correct	1415 ms	1912 KB	Output is correct

Submission #254308

Compilation message

Subtask #1 18.0 / 18.0

Subtask #2 18.0 / 18.0

Subtask #3 18.0 / 18.0

Subtask #4 18.0 / 18.0

Subtask #5 18.0 / 18.0

Subtask #6 10.0 / 10.0

Subtask #1
18.0 / 18.0

Subtask #2
18.0 / 18.0

Subtask #3
18.0 / 18.0

Subtask #4
18.0 / 18.0

Subtask #5
18.0 / 18.0

Subtask #6
10.0 / 10.0