oj.uz

Submission #1101979

# Submission time Handle Problem Language Result Execution time Memory
1101979 2024-10-17T08:57:41 Z AnhPham Nile (IOI24_nile) C++17
17 / 100
 2000 ms 4808 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;

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 <long long> dp(N, 0);
        dp[0] = A[0];
        for (int i = 1; i < N; ++i) {
            dp[i] = dp[i - 1] + A[i];
            long long 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
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 520 KB Output is correct
2 Correct 18 ms 568 KB Output is correct
3 Correct 21 ms 336 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 336 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 4800 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 2040 ms 4808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 520 KB Output is correct
2 Correct 18 ms 568 KB Output is correct
3 Correct 21 ms 336 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 336 KB Output is correct
7 Correct 15 ms 592 KB Output is correct
8 Correct 16 ms 584 KB Output is correct
9 Correct 15 ms 584 KB Output is correct
10 Correct 16 ms 336 KB Output is correct
11 Correct 15 ms 688 KB Output is correct
12 Correct 15 ms 336 KB Output is correct

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 520 KB Output is correct
2 Correct 18 ms 568 KB Output is correct
3 Correct 21 ms 336 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 336 KB Output is correct
7 Execution timed out 2059 ms 4800 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 2040 ms 4808 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 18 ms 520 KB Output is correct
3 Correct 18 ms 568 KB Output is correct
4 Correct 21 ms 336 KB Output is correct
5 Correct 18 ms 336 KB Output is correct
6 Correct 18 ms 336 KB Output is correct
7 Correct 18 ms 336 KB Output is correct
8 Execution timed out 2059 ms 4800 KB Time limit exceeded
9 Halted 0 ms 0 KB -