oj.uz

Submission #532809

# Submission time Handle Problem Language Result Execution time Memory
532809 2022-03-04T01:36:33 Z exopeng Cloud Computing (CEOI18_clo) C++14
100 / 100
 1529 ms 2036 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>,
rb_tree_tag, tree_order_statistics_node_update>;

#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define f first
#define ll long long
#define ld long double
#define s second
#define pii pair<int,int>
#define pdd pair<double,double>
#define pll pair<ll,ll>
#define is insert
const long long INF = 1e18;
const long long MOD = 1e9+7;
const int MAXN = 2001;
//store test cases here
/*

4
4 2200 700
2 1800 10
20 2550 9999
4 2000 750
3
1 1500 300
6 1900 1500
3 2400 4550
*/
int n,m;
//clock rate, # of cores, and price
pair<int,pii> co[MAXN];
pair<int,pii> od[MAXN];
ll dp[2][2001][51];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<2;i++){
        for(int j=0;j<2001;j++){
            for(int k=1;k<51;k++){
                dp[i][j][k]=-1*INF;
            }
        }
    }
    for(int i=0;i<n;i++){
        cin>>co[i].f>>co[i].s.f>>co[i].s.s;
        swap(co[i].f,co[i].s.f);
    }
    cin>>m;
    for(int i=0;i<m;i++){
        cin>>od[i].f>>od[i].s.f>>od[i].s.s;
        swap(od[i].f,od[i].s.f);
    }
    sort(co,co+n,greater<pair<int,pii>>());
    sort(od,od+m,greater<pair<int,pii>>());
    ll mx=0;
    for(int i=0;i<=n;i++){
        int ix=i%2;
        int nx=(ix+1)%2;
        for(int j=0;j<=m;j++){
            for(int k=0;k<=50;k++){
                if(j){
                    dp[ix][j][k]=max(dp[ix][j][k],dp[ix][j-1][k]);
                }
                mx=max(mx,dp[ix][j][k]);
                if(j==m||dp[ix][j][k]==-1*INF){
                    continue;
                }
                if(k>=od[j].s.f){
                    dp[ix][j+1][k-od[j].s.f]=
                    max(dp[ix][j+1][k-od[j].s.f],dp[ix][j][k]+od[j].s.s);

                }else if(i!=n){
                    if(co[i].f>=od[j].f){
                        if(co[i].s.f+k>=od[j].s.f){
                            dp[nx][j+1][co[i].s.f+k-od[j].s.f]
                            =max(dp[nx][j+1][co[i].s.f+k-od[j].s.f],
                                dp[ix][j][k]+od[j].s.s-co[i].s.s);    
                        }else{
                        //can still buy however
                            dp[nx][j][co[i].s.f+k]=max(dp[nx][j][co[i].s.f+k],
                                dp[ix][j][k]-co[i].s.s);
                        }
                        
                    }

                }
            }
        }
        for(int j=0;j<=m;j++){
            dp[nx][j][0]=max(dp[nx][j][0],dp[ix][j][0]);
            dp[ix][j][0]=0;
            for(int k=1;k<=50;k++){
                dp[nx][j][k]=max(dp[nx][j][k],dp[ix][j][k]);
                dp[ix][j][k]=-1*INF;
            }
        }
    }
    cout<<mx<<'\n';
    return 0;
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 10 ms 1868 KB Output is correct
6 Correct 6 ms 1868 KB Output is correct
7 Correct 9 ms 1984 KB Output is correct
8 Correct 14 ms 1876 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 1 ms 1856 KB Output is correct
5 Correct 5 ms 1868 KB Output is correct
6 Correct 4 ms 1868 KB Output is correct
7 Correct 10 ms 1992 KB Output is correct
8 Correct 11 ms 1868 KB Output is correct
9 Correct 11 ms 1868 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1856 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 2 ms 1868 KB Output is correct
4 Correct 2 ms 1840 KB Output is correct
5 Correct 5 ms 1868 KB Output is correct
6 Correct 5 ms 1936 KB Output is correct
7 Correct 9 ms 1860 KB Output is correct
8 Correct 9 ms 1868 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1868 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 5 ms 1868 KB Output is correct
4 Correct 11 ms 1956 KB Output is correct
5 Correct 1311 ms 1996 KB Output is correct
6 Correct 1492 ms 1996 KB Output is correct
7 Correct 1529 ms 1996 KB Output is correct
8 Correct 1479 ms 2000 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 2 ms 1852 KB Output is correct
3 Correct 49 ms 1916 KB Output is correct
4 Correct 154 ms 1952 KB Output is correct
5 Correct 1117 ms 2000 KB Output is correct
6 Correct 1509 ms 1972 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1868 KB Output is correct
2 Correct 2 ms 1868 KB Output is correct
3 Correct 1 ms 1868 KB Output is correct
4 Correct 2 ms 1868 KB Output is correct
5 Correct 10 ms 1868 KB Output is correct
6 Correct 6 ms 1868 KB Output is correct
7 Correct 9 ms 1984 KB Output is correct
8 Correct 14 ms 1876 KB Output is correct
9 Correct 1 ms 1868 KB Output is correct
10 Correct 1 ms 1868 KB Output is correct
11 Correct 1 ms 1868 KB Output is correct
12 Correct 1 ms 1856 KB Output is correct
13 Correct 5 ms 1868 KB Output is correct
14 Correct 4 ms 1868 KB Output is correct
15 Correct 10 ms 1992 KB Output is correct
16 Correct 11 ms 1868 KB Output is correct
17 Correct 11 ms 1868 KB Output is correct
18 Correct 1 ms 1856 KB Output is correct
19 Correct 1 ms 1868 KB Output is correct
20 Correct 2 ms 1868 KB Output is correct
21 Correct 2 ms 1840 KB Output is correct
22 Correct 5 ms 1868 KB Output is correct
23 Correct 5 ms 1936 KB Output is correct
24 Correct 9 ms 1860 KB Output is correct
25 Correct 9 ms 1868 KB Output is correct
26 Correct 2 ms 1868 KB Output is correct
27 Correct 1 ms 1868 KB Output is correct
28 Correct 5 ms 1868 KB Output is correct
29 Correct 11 ms 1956 KB Output is correct
30 Correct 1311 ms 1996 KB Output is correct
31 Correct 1492 ms 1996 KB Output is correct
32 Correct 1529 ms 1996 KB Output is correct
33 Correct 1479 ms 2000 KB Output is correct
34 Correct 1 ms 1868 KB Output is correct
35 Correct 2 ms 1852 KB Output is correct
36 Correct 49 ms 1916 KB Output is correct
37 Correct 154 ms 1952 KB Output is correct
38 Correct 1117 ms 2000 KB Output is correct
39 Correct 1509 ms 1972 KB Output is correct
40 Correct 74 ms 1944 KB Output is correct
41 Correct 275 ms 1952 KB Output is correct
42 Correct 287 ms 1868 KB Output is correct
43 Correct 538 ms 1996 KB Output is correct
44 Correct 528 ms 2000 KB Output is correct
45 Correct 520 ms 2036 KB Output is correct
46 Correct 126 ms 1868 KB Output is correct
47 Correct 284 ms 2008 KB Output is correct
48 Correct 285 ms 1996 KB Output is correct