# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1108691 | akzytr | 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>
#define ve vector
#define pb push_back
#define ar array
#define ll long long
#define sz(x) (int)(x.size())
using namespace std;
ve<ll> calculate_costs(ve<int> W, ve<int> A, ve<int> B, ve<int> Q) {
ve<ll> ans;
int N = sz(W);
array<ll, 2> W2[N];
for(int i = 0; i < N; i++) {
W2[i] = {W[i], i};
}
sort(W2, W2 + N);
for(int diff : Q) {
ll tc = 0;
ve<ve<int>> ccs;
ve<int> curcc;
for(int i = 0; i < N; i++) {
if(i != 0 && W2[i][0] - W2[i - 1][0] > diff) {
ccs.pb(curcc);
ve<int> nc;
curcc = nc;
}
curcc.pb(i);
}
ccs.pb(curcc);
for(auto i : ccs) {
assert(sz(i) >= 1);
ll tb = 0;
for(int j : i) {
int idx = W2[j][1];
tb += B[idx];
}
if(sz(i) % 2) {
int sz_cc = sz(i);
int idxone = W2[i[0]][1];
int idxn = W2[i[sz_cc - 1]][1];
ll mi = 91e18;
for(int j = 0; j < sz_cc; j++) {
if(j % 2 == 0) {
mi = min(mi, tb - B[idx] + A[idx]);
} else if(W2[i[j + 1]][0] - W2[i[j - 1]][0] <= diff) {
int idx = W2[i[j]][1];
mi = min(mi, tb - B[idx] + A[idx]);
}
}
tb = mi;
}
tc += tb;
}
ans.pb(tc);
}
return ans;
}
// int main() {
// int N;
// cin >> N;
//
// ve<int> w;
// ve<int> a;
// ve<int> b;
// ve<int> q;
// for(int i = 0; i < N; i++) {
// int x, y, z;
// cin >> x >> y >> z;
// w.pb(x);
// a.pb(y);
// b.pb(z);
// }
// int Q;
// cin >> Q;
// for(int i = 0; i < Q; i++) {
// int x;
// cin >> x;
// q.pb(x);
// }
//
// calculate_costs(w, a, b, q);
// }