oj.uz

답안 #1099756

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1099756 2024-10-12T05:11:11 Z model_code 나일강 (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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -