제출 #1198667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198667		tamyte	나일강 (IOI24_nile)	C++20	67 / 100	2094 ms	6216 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;



std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
  int Q = (int)E.size();
  vector<int> pool;
  int N = W.size();
  vector<int> order(N);
  iota(begin(order), end(order), 0);
  sort(begin(order), end(order), [&](int x, int y) {
       return W[x] < W[y];
    });
    vector<ll> ps(N + 1);
    for (int i = 0; i < N; ++i) {
        ps[i] = A[order[i]];
        if (i) ps[i] += ps[i - 1];
    }
//    for (int i = 0; i < N; ++i) {
//        cout << W[order[i]] << " ";
//
//    }
//    cout << "\n";
//    for (int i = 0; i < N; ++i) {
//        cout << ps[i] << " ";
//    }
//    cout << "\n";
    vector<ll> R(Q);
    for (int _ = 0; _ < Q; ++_) {
        ll bound = E[_];
        vector<ll> dp(N + 1, LLONG_MAX);
        dp[0] = 0;
        for (int j = 0; j < N; ++j) {
            for (int k = j + 1; k < min(N, j + 3) && abs(W[order[j]] - W[order[k]]) <= bound; ++k) {
                ll ndp = dp[j] + ps[k] - (j == 0 ? 0 : ps[j - 1]) - A[order[j]] - A[order[k]] + B[order[j]]
                    + B[order[k]];
                dp[k + 1] = min(dp[k + 1], ndp);
            }
            dp[j + 1] = min(dp[j + 1], dp[j] + A[order[j]]);
        }
//        for (int i = 0; i <= N; ++i) {
//            cout << dp[i] << " ";
//        }
//        cout << "\n";
        R[_] = dp[N];
    }
    return R;
}

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