oj.uz

Submission #944462

# Submission time Handle Problem Language Result Execution time Memory
944462 2024-03-12T18:05:04 Z Captain_Georgia Cloud Computing (CEOI18_clo) C++17
18 / 100
 371 ms 1164 KB 
#include <bits/stdc++.h>
using namespace std;

#define file \
            freopen("in.txt" , "r" , stdin); \
            freopen("out.txt" , "w" , stdout);


void test_case () {
    int n , m;
    cin >> n;
    int f[n] , c[n] , w[n];
    int sum = 0;
    for (int i = 0;i < n;i ++) {
        cin >> c[i] >> f[i] >> w[i];
    }
    cin >> m;
    int f_[m] , c_[m] , w_[m];
    set<int> s;
    s.insert(0);
    for (int i = 0;i < m;i ++) {
        cin >> c_[i] >> f_[i] >> w_[i];
        sum += c_[i];
        s.insert(f_[i]);
    }
    // cout << s.size() << "\n";
    vector<int> v(s.begin() , s.end());
    vector<pair<int , int>> g[m + 5] , g_[m + 5];
    for (int i = 0;i < n;i ++) {
        f[i] = lower_bound(v.begin() , v.end() , (int) *(-- s.upper_bound(f[i]))) - v.begin();
        // cout << f[i] << "  ";
        g[f[i]].push_back({c[i] , w[i]});
    }
    // cout << "\n";
    for (int i = 0;i < m;i ++) {
        // cout << f_[i] << "  ";
        f_[i] = lower_bound(v.begin() , v.end() , f_[i]) - v.begin();
        // cout << f_[i] << " || ";
        g_[f_[i]].push_back({c_[i] , w_[i]});
    }
    // cout << "\n";
    vector<int> dp(sum + 10 , 0);
    for (int i = 0;i <= m;i ++) {
        for (auto j : g_[i]) {
            for (int k = sum;k >= j.first;k --) {
                dp[k] = max(dp[k] , dp[k - j.first] +  j.second);
            }
        }
        for (auto j : g[i]) {
            for (int k = 0;k <= sum;k ++) {
                dp[k] = max(dp[k] , dp[min(k + j.first , sum)] - j.second);
            }
        }
    }
    cout << dp[0] << "\n";
}

int main () {

    // file
    int TIME = clock();

    int t = 1;
    // cin >> t;

    while (t --) {
        test_case();
    }

    cerr << "\nTime elapsed: " << (clock() - TIME) * 1000.0 / CLOCKS_PER_SEC << " ms\n";

}

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 69 ms 792 KB Output is correct
6 Incorrect 24 ms 780 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Incorrect 3 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 14 ms 604 KB Output is correct
5 Incorrect 171 ms 648 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
18.0 / 18.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 69 ms 792 KB Output is correct
6 Incorrect 24 ms 780 KB Output isn't correct
7 Halted 0 ms 0 KB -