| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1306842 | michael12 | 나일강 (IOI24_nile) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include "nile.h";
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define int long long
using namespace std;
const int maxn = 5e5;
vector<int> calculate_costs(
vector<int> W,
vector<int> A,
vector<int> B,
vector<int> E
) {
int N = W.size();
int Q = E.size();
vector<array<int,3>> at(N);
for (int i = 0; i < N; i++) {
at[i] = {W[i], A[i], B[i]};
}
sort(at.begin(), at.end());
int sm = 0;
for (int i = 0; i < N; i++) {
sm += at[i][1];
}
vector<int> rs(Q);
for (int qi = 0; qi < Q; qi++) {
int D = E[qi];
vector<int> dp(N, 0);
for (int i = 0; i < N; i++) {
if (i > 0) dp[i] = dp[i - 1];
for (int j = i - 1; j >= 0; j--) {
if (at[i][0] - at[j][0] > D) break;
int sv =
(int)at[i][1] + at[j][1]
- at[i][2] - at[j][2];
if (j > 0)
dp[i] = max(dp[i], dp[j - 1] + sv);
else
dp[i] = max(dp[i], sv);
}
}
rs[qi] = sm - dp[N - 1];
}
return rs;
}
