oj.uz

Submission #481890

# Submission time Handle Problem Language Result Execution time Memory
481890 2021-10-22T07:07:58 Z keertan Cloud Computing (CEOI18_clo) C++17
100 / 100
 597 ms 2892 KB 
/**
 * If you live in imaginary world when your imaginary situation encounter in 
 * real situation you can't enjoiy it because you have to do pending work.
 * {This pending work appeared because you wasted that time for your useless
 * imagianry thinking.}
 */
#include<bits/stdc++.h>
using namespace std;
#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
const int N=2e6+5;

int vis=0;
typedef struct A{
    int core;
    int rate;
    int price;
}node;
void solve(){
    int n;
    cin>>n;
    vector<node> z;
    node x;
    int mx=0;
    for (int i=0;i<n;i++){
        cin>>x.core>>x.rate>>x.price;
        x.price*=-1;
        z.push_back(x);
        mx+=x.core;
    }
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>x.core>>x.rate>>x.price;
        x.core*=-1;
        z.push_back(x);
    }
    sort(all(z),[&](node a,node b){
        if (a.rate==b.rate){return a.price<b.price;}
        return a.rate>b.rate;
    });   
    n=z.size();
    vector<vector<int>> dp(2,vector<int>(mx+1,INT64_MIN));
    dp[0][0]=dp[1][0]=0;
    for (int i=0;i<n;i++){
        int cur=i&1,prv=~i&1;
        for (int j=0;j<=mx;j++){
            int con=j-z[i].core;
            dp[cur][j]=dp[prv][j];
            if (0<=con && con<=mx && dp[prv][con]!=INT64_MIN){
            dp[cur][j]=max(dp[prv][j],z[i].price+dp[prv][con]);}
        }
    }
    int ans=0;
    for (int i=0;i<=mx;i++){ans=max(ans,dp[(n-1)&1][i]);}
    cout<<ans;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tq=1;
    //cin>>tq;
    for (;tq;tq--){solve();}
}
//is a bruteforce possible?
//think greedier, make more assumptions
// if we you find solution using loop to decrease complexity use bs
//stuck for more than 5 minutes? move on

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 332 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 34 ms 840 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 164 ms 1612 KB Output is correct
8 Correct 25 ms 588 KB Output is correct
9 Correct 202 ms 2380 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 216 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 11 ms 488 KB Output is correct
4 Correct 4 ms 332 KB Output is correct
5 Correct 249 ms 1740 KB Output is correct
6 Correct 483 ms 2636 KB Output is correct
7 Correct 467 ms 2636 KB Output is correct
8 Correct 545 ms 2508 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 31 ms 972 KB Output is correct
4 Correct 8 ms 444 KB Output is correct
5 Correct 506 ms 2636 KB Output is correct
6 Correct 533 ms 2632 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 332 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 34 ms 840 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 164 ms 1612 KB Output is correct
16 Correct 25 ms 588 KB Output is correct
17 Correct 202 ms 2380 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 204 KB Output is correct
21 Correct 0 ms 204 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 332 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 216 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 11 ms 488 KB Output is correct
29 Correct 4 ms 332 KB Output is correct
30 Correct 249 ms 1740 KB Output is correct
31 Correct 483 ms 2636 KB Output is correct
32 Correct 467 ms 2636 KB Output is correct
33 Correct 545 ms 2508 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 1 ms 332 KB Output is correct
36 Correct 31 ms 972 KB Output is correct
37 Correct 8 ms 444 KB Output is correct
38 Correct 506 ms 2636 KB Output is correct
39 Correct 533 ms 2632 KB Output is correct
40 Correct 36 ms 844 KB Output is correct
41 Correct 96 ms 1228 KB Output is correct
42 Correct 7 ms 460 KB Output is correct
43 Correct 501 ms 2888 KB Output is correct
44 Correct 504 ms 2884 KB Output is correct
45 Correct 597 ms 2892 KB Output is correct
46 Correct 3 ms 332 KB Output is correct
47 Correct 7 ms 524 KB Output is correct
48 Correct 6 ms 460 KB Output is correct