oj.uz

Submission #947195

# Submission time Handle Problem Language Result Execution time Memory
947195 2024-03-15T15:49:43 Z lulwpop Cloud Computing (CEOI18_clo) C++14
54 / 100
 350 ms 1872 KB 
#include <bits/stdc++.h>
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define pw(x) (1ll << x)
#define pb push_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define vec vector

using namespace std;

template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

inline void solve () {
    int n; cin >> n;
    vector <array <long long, 4>> ful;
    vector <long long> c (n), f (n), v (n);
    for (int i = 0; i < n; ++i) {
        cin >> c[i] >> f[i] >> v[i];
        ful.pb({f[i], 0, c[i], v[i]});
    }
    int m; cin >> m;
    vector <long long> qc (m), qf (m), qv (m);
    for (int i = 0; i < m; ++i) {
        cin >> qc[i] >> qf[i] >> qv[i];
        ful.pb({qf[i], 1, qc[i], qv[i]});
    }   
    const int MX = 60 * n + 51;
    // const int MX = 10;
    vector <ll> dp (MX, -2e18); 
    dp[0] = 0;
    sort(all(ful)); 
    while (sz(ful)) {
        auto [f, type, c, v] = ful.back();
        if (type == 0) {
            for (int i = MX - c; i >= 0; --i) {
                // cout << i << " " << dp[i] << " " << v << " " << dp[i + c] << endl;
                umax(dp[i + c], dp[i] - v);
                // cout << i << " " << dp[i] << " " << v << " " << dp[i + c] << endl;
            }
        }
        else {
            for (int i = c; i < MX; ++i) {
                // cout << i << " " << dp[i] << " " << v << " " << dp[i - c] << endl;
                umax(dp[i - c], dp[i] + v);
                // cout << i << " " << dp[i] << " " << v << " " << dp[i - c] << endl;
            }
        }
        ful.pop_back();
    }
    // for (auto i : dp) cout << i << " "; cout << endl;
    cout << *max_element(all(dp));
}

signed main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message

clo.cpp: In function 'void solve()':
clo.cpp:41:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |         auto [f, type, c, v] = ful.back();
      |              ^

Subtask #1
18.0 / 18.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 32 ms 860 KB Output is correct
6 Correct 31 ms 860 KB Output is correct
7 Correct 156 ms 1372 KB Output is correct
8 Correct 150 ms 1368 KB Output is correct
9 Incorrect 152 ms 1368 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 5 ms 604 KB Output is correct
8 Correct 5 ms 600 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 21 ms 604 KB Output is correct
4 Correct 60 ms 860 KB Output is correct
5 Correct 350 ms 1628 KB Output is correct
6 Correct 311 ms 1872 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 604 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 1 ms 344 KB Output is correct
13 Correct 32 ms 860 KB Output is correct
14 Correct 31 ms 860 KB Output is correct
15 Correct 156 ms 1372 KB Output is correct
16 Correct 150 ms 1368 KB Output is correct
17 Incorrect 152 ms 1368 KB Output isn't correct
18 Halted 0 ms 0 KB -