oj.uz

Submission #1101974

# Submission time Handle Problem Language Result Execution time Memory
1101974 2024-10-17T08:54:26 Z AnhPham Nile (IOI24_nile) C++17
0 / 100
 2000 ms 6860 KB 
#include <bits/stdc++.h>
#include "nile.h"
// #ifdef OP_DEBUG
//     #include <algo/debug.h>
// #else
//     #define debug(...) 26
// #endif

using namespace std;
// template <class Fun> class y_combinator_result {
//     Fun fun_;
// public:
//     template <class T> explicit y_combinator_result(T &&fun): fun_(std::forward <T> (fun)) {}
//     template <class ...Args> decltype(auto) operator()(Args &&...args) { return fun_(std::ref(*this), std::forward <Args> (args)...); }
// };
// template <class Fun> decltype(auto) y_combinator(Fun &&fun) { return y_combinator_result <std::decay_t <Fun>> (std::forward <Fun> (fun)); }

// #define int 	long long
#define eb      emplace_back
#define sz(v)   (int)(v).size()
#define all(v)  (v).begin(), (v).end()
// #define TcT     template <class T

// const   int     MOD = (int)1e9 + 7, INF = (int)4e18 + 18;

// TcT>            bool minimize(T &lhs, const T &rhs) { return rhs < lhs ? lhs = rhs, 1 : 0; }
// TcT>            bool maximize(T &lhs, const T &rhs) { return rhs > lhs ? lhs = rhs, 1 : 0; }

// void solve();

// int32_t main() {
//     cin.tie(nullptr), cout.tie(nullptr) -> sync_with_stdio(false);
//     int testcases = 1;

// #define multitest 0
//     if (multitest) { cin >> testcases; } for (; testcases--;) { solve(); }
// }

// /* [Pham Hung Anh - 12I - Tran Hung Dao High School for Gifted Student] */

const int mxN = 1e5 + 5;

int dp[mxN];

vector <long long> calculate_costs(vector <int> W, vector <int> A, vector <int> B, vector <int> E) {
    int N = sz(W), Q = sz(E);
    vector <tuple <int, int, int>> queries;
    for (int i = 0; i < N; ++i)
        queries.eb(W[i], A[i], B[i]);
    
    sort(all(queries));

    for (int i = 0; i < N; ++i) {
        auto [w, a, b] = queries[i];
        W[i] = w, A[i] = a, B[i] = b;
    }

    vector <long long> ans;
    for (int q = 0; q < Q; ++q) {
        vector <int> dp(N, 0);
        dp[0] = A[0];
        for (int i = 1; i < N; ++i) {
            dp[i] = dp[i - 1] + A[i];
            int sum = 0;
            for (int j = i - 1; j >= 0; --j) {
                if (W[i] - W[j] <= E[q])
                    dp[i] = min(dp[i], (j == 0 ? 0 : dp[j - 1]) + B[i] + B[j] + sum);

                sum += A[j];
            }
        }

        ans.emplace_back(dp[N - 1]);
    }

    return ans;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 6.0

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

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2043 ms 6860 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 2050 ms 5444 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

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

Subtask #5
0.0 / 20.0

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

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 5444 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 Incorrect 15 ms 580 KB Output isn't correct
3 Halted 0 ms 0 KB -