# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1106034 | jadai007 | Nile (IOI24_nile) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "nile.h"
#define int long long
using namespace std;
vector<int> 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>> Ws;
vector<int> ans;
for(int i = 0; i < N; ++i) Ws.emplace_back(W[i], A[i], B[i]);
sort(W.begin(), W.end());
for(int i = 0; i < N; ++i) W[i] = get<0>(Ws[i]), A[i] = get<1>(Ws[i]), B[i] = get<2>(Ws[i]);
for(int i = 0; i < q; ++i){
int d = E[i];
vector<int> dp(N+1, LLONG_MAX);
for(int i = 0; i < N; ++i){
if(i == 0) dp[i] = A[i];
else if(i == 1){
if(W[i] - W[i - 1] <= d) dp[i] = B[i] + B[i - 1];
else dp[i] = dp[i - 1] + A[i];
}
else{
dp[i] = dp[i - 1] + A[i];
if(i >= 3) dp[i] = min(dp[i], B[i] + A[i - 1] + B[i - 2] + dp[i - 3]);
else dp[i] = min(dp[i], B[i] + A[i - 1] + B[i - 2]);
}
}
ans.push_back(dp[N - 1]);
}
return ans;
}