oj.uz

Submission #1109936

# Submission time Handle Problem Language Result Execution time Memory
1109936 2024-11-08T07:24:46 Z JeffLegendPower Nile (IOI24_nile) C++17
17 / 100
 2000 ms 5712 KB 
// Problem link here: https://oj.uz/problem/view/IOI24_nile

// #include "nile.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define plli pair<ll, int>
#define pll pair<ll, ll>
#define pii pair<int, int>
// Usage: FOR(i, 0, N) {...}
#define FOR(i, start, end) for(int i = start; i < end; i++)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a, b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a, b)(rng); }

struct artif {
    ll A, B, W;
};


std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
    int Q = (int) E.size();
    std::vector<long long> R(Q, 0);

    int N = (int) W.size();

    artif facts[N];
    for (int i = 0; i < N; i++) {
        facts[i].W = W[i];
        facts[i].A = A[i];
        facts[i].B = B[i];
    }

    sort(facts, facts + N, [](artif one, artif two) {
        return one.W > two.W;
    });

    for (int q = 0; q < Q; q++) {
        ll D = E[q];

        vector<ll> dp(N + 1, 0);
        dp[1] = facts[0].A;

        for (int i = 1; i < N; i++) {
            dp[i + 1] = dp[i] + facts[i].A;

            ll totalB = 0;
            ll minsave = 1e18;
            for (int j = i - 1; j >= 0; j--) {
                if (facts[j].W - facts[i].W > D) break;
                int diff = i - j - 1;
                
                ll cost = facts[i].B + facts[j].B + totalB;
                if (diff&1) cost += minsave;

                dp[i + 1] = min(dp[i + 1], dp[j] + cost);

                totalB += facts[j].B;
                minsave = min(minsave, facts[j].A - facts[j].B);
            }
        }

        R[q] = dp[N];
    }

    return R;
}

// int main() {
//     int N; cin >> N;

//     artif facts[N];
//     for (int i = 0; i < N; i++) cin >> facts[i].W >> facts[i].A >> facts[i].B;

//     sort(facts, facts + N, [](artif one, artif two) {
//         return one.W > two.W;
//     });

//     int Q; cin >> Q;

//     while (Q--) {
//         ll D; cin >> D;

//         vector<ll> dp(N + 1, 0);
//         dp[1] = facts[0].A;

//         for (int i = 1; i < N; i++) {
//             dp[i + 1] = dp[i] + facts[i].A;

//             ll totalB = 0;
//             ll minsave = 1e18;
//             for (int j = i - 1; j >= 0; j--) {
//                 if (facts[j].W - facts[i].W > D) break;
//                 int diff = i - j - 1;
                
//                 ll cost = facts[i].B + facts[j].B + totalB;
//                 if (diff&1) cost += minsave;

//                 dp[i + 1] = min(dp[i + 1], dp[j] + cost);

//                 totalB += facts[j].B;
//                 minsave = min(minsave, facts[j].A - facts[j].B);
//             }
//         }

//         cout << dp[N] << endl;
//         // for (int i = 1; i <= N; i++) cout << dp[i] << " ";
//     }
// }

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 336 KB Output is correct
2 Correct 24 ms 716 KB Output is correct
3 Correct 18 ms 336 KB Output is correct
4 Correct 18 ms 336 KB Output is correct
5 Correct 18 ms 592 KB Output is correct
6 Correct 18 ms 596 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 5712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 5712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 336 KB Output is correct
2 Correct 24 ms 716 KB Output is correct
3 Correct 18 ms 336 KB Output is correct
4 Correct 18 ms 336 KB Output is correct
5 Correct 18 ms 592 KB Output is correct
6 Correct 18 ms 596 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 7 ms 592 KB Output is correct
9 Correct 6 ms 592 KB Output is correct
10 Correct 5 ms 592 KB Output is correct
11 Correct 6 ms 592 KB Output is correct
12 Correct 5 ms 592 KB Output is correct

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 336 KB Output is correct
2 Correct 24 ms 716 KB Output is correct
3 Correct 18 ms 336 KB Output is correct
4 Correct 18 ms 336 KB Output is correct
5 Correct 18 ms 592 KB Output is correct
6 Correct 18 ms 596 KB Output is correct
7 Execution timed out 2054 ms 5712 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2035 ms 5712 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 27 ms 336 KB Output is correct
3 Correct 24 ms 716 KB Output is correct
4 Correct 18 ms 336 KB Output is correct
5 Correct 18 ms 336 KB Output is correct
6 Correct 18 ms 592 KB Output is correct
7 Correct 18 ms 596 KB Output is correct
8 Execution timed out 2054 ms 5712 KB Time limit exceeded
9 Halted 0 ms 0 KB -