oj.uz

Submission #1099756

# Submission time Handle Problem Language Result Execution time Memory
1099756 2024-10-12T05:11:11 Z model_code Nile (IOI24_nile) C++17
17 / 100
 996 ms 2097152 KB 
// time_limit_and_runtime_error/hazem_dp_qn2_mle.cpp

#include "bits/stdc++.h"
#include "nile.h"
using namespace std;

const long long INF = 1e14;

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int n = W.size();
    int q = E.size();

    vector<int> ordW(n);
    iota(ordW.begin() ,ordW.end() ,0);
    sort(ordW.begin() ,ordW.end() ,[&](int i ,int j){
        return W[i] < W[j];
    });
    vector<int> w(n), a(n), b(n);
    for(int i = 0; i < n; i++){
        int j = ordW[i];
        w[i] = W[j];
        a[i] = A[j];
        b[i] = B[j];
    }

    auto solve = [&](int d){
        vector<vector<long long>> dp(n+1, vector<long long>(n+1, INF));
        dp[n][n] = 0;
        for(int i = n - 1; i >= 0; i--){
            dp[i][n] = min(a[i] + dp[i+1][n], b[i] + dp[i+1][i]);
            for(int j = i - 1; j >= 0 && w[i] - w[j] <= d; j--)
                dp[i][j] = min(a[i] + dp[i+1][j], b[i] + dp[i+1][n]);
        }
        return dp[0][n];
    };

    vector<long long> R(q);
    for(int i = 0; i < q; i++)
        R[i] = solve(E[i]);
    return R;
}

Subtask #0
0.0 / 0.0

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

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 31916 KB Output is correct
2 Correct 69 ms 32004 KB Output is correct
3 Correct 70 ms 32012 KB Output is correct
4 Correct 74 ms 31980 KB Output is correct
5 Correct 71 ms 32036 KB Output is correct
6 Correct 68 ms 31980 KB Output is correct

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 947 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 996 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 31916 KB Output is correct
2 Correct 69 ms 32004 KB Output is correct
3 Correct 70 ms 32012 KB Output is correct
4 Correct 74 ms 31980 KB Output is correct
5 Correct 71 ms 32036 KB Output is correct
6 Correct 68 ms 31980 KB Output is correct
7 Correct 68 ms 31916 KB Output is correct
8 Correct 71 ms 31916 KB Output is correct
9 Correct 72 ms 31960 KB Output is correct
10 Correct 67 ms 31924 KB Output is correct
11 Correct 67 ms 31920 KB Output is correct
12 Correct 67 ms 31964 KB Output is correct

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 31916 KB Output is correct
2 Correct 69 ms 32004 KB Output is correct
3 Correct 70 ms 32012 KB Output is correct
4 Correct 74 ms 31980 KB Output is correct
5 Correct 71 ms 32036 KB Output is correct
6 Correct 68 ms 31980 KB Output is correct
7 Runtime error 947 ms 2097152 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 996 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 71 ms 31916 KB Output is correct
3 Correct 69 ms 32004 KB Output is correct
4 Correct 70 ms 32012 KB Output is correct
5 Correct 74 ms 31980 KB Output is correct
6 Correct 71 ms 32036 KB Output is correct
7 Correct 68 ms 31980 KB Output is correct
8 Runtime error 947 ms 2097152 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -