oj.uz

Submission #968812

# Submission time Handle Problem Language Result Execution time Memory
968812 2024-04-24T06:34:57 Z dosts Cloud Computing (CEOI18_clo) C++17
72 / 100
 927 ms 3748 KB 
//Dost SEFEROĞLU
#pragma GCC optimize("O3,unroll-loops,Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " << 
#define vi vector<int>
const int N = 2e7+1,inf = 2e18,MOD = 1e9+7;

struct Order{
    int core,power,price;
};

void solve() {
    int n;
    cin >> n;
    vector<Order> orders;
    for (int i=1;i<=n;i++) {
        int c,f,p;
        cin >> c >> f >> p;
        orders.push_back({c,f,-p});
    }
    int m;
    cin >> m;
    for (int i=1;i<=m;i++) {
        int c,f,p;
        cin >> c >> f >> p;
        orders.push_back({-c,f,p});
    }    
    sort(orders.begin(),orders.end(),[&](Order o1,Order o2) {
        return o1.power > o2.power;
    });
    
    n = n+m;
    int dp[200001],dp2[200001];
    for (int i=0;i<=200000;i++) dp[i] = dp2[i] = -inf;
    dp2[0] = 0;
    for (int i=0;i<n;i++) {
        for (int j=0;j<=200000;j++) dp[j] = -inf;
        for (int c = 0;c<=200000;c++) {
            if (dp2[c] == -inf) continue;
            dp[c] = max(dp[c],dp2[c]);
            if (c+orders[i].core >= 0 && c+orders[i].core <= 200000) {
                dp[c+orders[i].core] =  max(dp[c+orders[i].core],dp2[c]+orders[i].price);
            }
        }
        for (int j=0;j<=200000;j++) dp2[j] = dp[j];
    }
    cout << max(0ll,*max_element(dp2,dp2+200001)) << '\n';
}
                
                            
signed main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t; 
    while (t --> 0) solve();
}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 24 ms 3416 KB Output is correct
4 Correct 35 ms 3416 KB Output is correct
5 Correct 295 ms 3416 KB Output is correct
6 Correct 308 ms 3676 KB Output is correct
7 Correct 318 ms 3676 KB Output is correct
8 Correct 335 ms 3648 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 4 ms 3420 KB Output is correct
3 Correct 19 ms 3420 KB Output is correct
4 Correct 19 ms 3420 KB Output is correct
5 Correct 154 ms 3672 KB Output is correct
6 Correct 150 ms 3668 KB Output is correct
7 Correct 387 ms 3420 KB Output is correct
8 Correct 341 ms 3672 KB Output is correct
9 Correct 398 ms 3672 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3416 KB Output is correct
2 Correct 7 ms 3420 KB Output is correct
3 Correct 30 ms 3420 KB Output is correct
4 Correct 30 ms 3416 KB Output is correct
5 Correct 59 ms 3584 KB Output is correct
6 Correct 80 ms 3420 KB Output is correct
7 Correct 81 ms 3416 KB Output is correct
8 Correct 78 ms 3416 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3428 KB Output is correct
2 Correct 5 ms 3416 KB Output is correct
3 Correct 253 ms 3420 KB Output is correct
4 Incorrect 283 ms 3676 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3416 KB Output is correct
2 Correct 27 ms 3420 KB Output is correct
3 Correct 149 ms 3420 KB Output is correct
4 Correct 319 ms 3672 KB Output is correct
5 Correct 805 ms 3748 KB Output is correct
6 Correct 927 ms 3748 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3420 KB Output is correct
2 Correct 3 ms 3420 KB Output is correct
3 Correct 24 ms 3416 KB Output is correct
4 Correct 35 ms 3416 KB Output is correct
5 Correct 295 ms 3416 KB Output is correct
6 Correct 308 ms 3676 KB Output is correct
7 Correct 318 ms 3676 KB Output is correct
8 Correct 335 ms 3648 KB Output is correct
9 Correct 3 ms 3420 KB Output is correct
10 Correct 4 ms 3420 KB Output is correct
11 Correct 19 ms 3420 KB Output is correct
12 Correct 19 ms 3420 KB Output is correct
13 Correct 154 ms 3672 KB Output is correct
14 Correct 150 ms 3668 KB Output is correct
15 Correct 387 ms 3420 KB Output is correct
16 Correct 341 ms 3672 KB Output is correct
17 Correct 398 ms 3672 KB Output is correct
18 Correct 7 ms 3416 KB Output is correct
19 Correct 7 ms 3420 KB Output is correct
20 Correct 30 ms 3420 KB Output is correct
21 Correct 30 ms 3416 KB Output is correct
22 Correct 59 ms 3584 KB Output is correct
23 Correct 80 ms 3420 KB Output is correct
24 Correct 81 ms 3416 KB Output is correct
25 Correct 78 ms 3416 KB Output is correct
26 Correct 5 ms 3428 KB Output is correct
27 Correct 5 ms 3416 KB Output is correct
28 Correct 253 ms 3420 KB Output is correct
29 Incorrect 283 ms 3676 KB Output isn't correct
30 Halted 0 ms 0 KB -