제출 #1208822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1208822		sula2	나일강 (IOI24_nile)	C++20	17 / 100	2095 ms	4980 KiB

nile

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define popcount(x) __builtin_popcountll(x)
using namespace std;
using namespace chrono;

long long solve(vector<int> W, vector<int> A,
                vector<int> B, int D) {
    int n = W.size();
    vector<int> ind(n);
    iota(all(ind), 0);
    sort(all(ind), [&](int i, int j) { return W[i] < W[j]; });
    vector<long long> dp(n);
    dp[0] = A[ind[0]];
    for (int i = 1; i < n; i++) {
        dp[i] = dp[i-1] + A[ind[i]];
        long long sum = 0;
        for (int j = i-1; j >= 0 && W[ind[i]] - W[ind[j]] <= D; j--) {
            dp[i] = min(dp[i], (j == 0 ? 0 : dp[j-1]) + B[ind[j]] + B[ind[i]] + sum);
            sum += A[ind[j]];
        }
    }
    return dp[n-1];
}

vector<long long> calculate_costs(
        vector<int> W, vector<int> A,
        vector<int> B, vector<int> E
        ) {
    int n = W.size(), q = E.size();
    vector<long long> res(q);
    for (int i = 0; i < q; i++) {
        res[i] = solve(W, A, B, E[i]);
    }
    return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 11 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18