oj.uz

Submission #1109418

# Submission time Handle Problem Language Result Execution time Memory
1109418 2024-11-06T16:13:29 Z Trisanu_Das Nile (IOI24_nile) C++17
17 / 100
 2000 ms 7368 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector <ll> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = W.size(), Q = E.size();
    vector <tuple <int, int, int>> items;
    for (int i = 0; i < N; i++) items.push_back(make_tuple(W[i], A[i], B[i]));
    sort(items.begin(), items.end());
    for (int i = 0; i < N; ++i) {
        auto [w, a, b] = items[i];
        W[i] = w, A[i] = a, B[i] = b;
    }
    vector <ll> ans;
    for (int q = 0; q < Q; q++) {
        vector <ll> dp(N, 0);
        dp[0] = A[0];
        for (int i = 1; i < N; ++i) {
            dp[i] = dp[i - 1] + A[i];
            ll 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.push_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 17 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct
3 Correct 17 ms 564 KB Output is correct
4 Correct 17 ms 336 KB Output is correct
5 Correct 17 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2063 ms 7368 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 2051 ms 5824 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct
3 Correct 17 ms 564 KB Output is correct
4 Correct 17 ms 336 KB Output is correct
5 Correct 17 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 10 ms 336 KB Output is correct
8 Correct 10 ms 584 KB Output is correct
9 Correct 10 ms 516 KB Output is correct
10 Correct 11 ms 336 KB Output is correct
11 Correct 10 ms 452 KB Output is correct
12 Correct 11 ms 592 KB Output is correct

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 336 KB Output is correct
2 Correct 16 ms 336 KB Output is correct
3 Correct 17 ms 564 KB Output is correct
4 Correct 17 ms 336 KB Output is correct
5 Correct 17 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Execution timed out 2063 ms 7368 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 2051 ms 5824 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 17 ms 336 KB Output is correct
3 Correct 16 ms 336 KB Output is correct
4 Correct 17 ms 564 KB Output is correct
5 Correct 17 ms 336 KB Output is correct
6 Correct 17 ms 336 KB Output is correct
7 Correct 17 ms 336 KB Output is correct
8 Execution timed out 2063 ms 7368 KB Time limit exceeded
9 Halted 0 ms 0 KB -