Submission #1245442

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245442		franuch	Nile (IOI24_nile)	C++20	67 / 100	2092 ms	9032 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
const ll INF = 1e17;

ll n, q;
vc<ll> w, a, b;
vc<pll> ques;
vc<ll> res;

ll solve(ll D) {
	vc<ll> ord(n);
	iota(all(ord), 0);
	sort(all(ord), [&](ll i, ll j) {
		return w[i] < w[j];
	});
	ll prw = -INF;
	ll best = INF;
	ll sum = 0;
	ll par = 0;
	ll ans = 0;
	for (ll j = 0; j < n; j++) {
		ll i = ord[j];
		if (w[i] - prw > D) {
			if (par % 2 == 0)
				ans += sum;
			else
				ans += sum + best;
			best = INF;
			sum = 0;
			par = 0;
		}
		if (par == 0 or (j + 1 < n and w[ord[j + 1]] - prw <= D))
			best = min(best, a[i] - b[i]);
		prw = w[i];
		sum += b[i];
		par ^= 1;
	}
	if (par % 2 == 0)
		ans += sum;
	else
		ans += sum + best;
	return ans;
}

void program() {
	res.resize(q);
	for (ll i = 0; i < q; i++)
		res[i] = solve(ques[i].st);
}

vc<ll> calculate_costs(vc<int> W, vc<int> A, vc<int> B, vc<int> E) {
	n = sz(W);
	q = sz(E);
	w.assign(all(W));
	a.assign(all(A));
	b.assign(all(B));
	ques.resize(q);
	for (ll i = 0; i < q; i++)
		ques[i] = {E[i], i};
	program();
	return res;
}

• 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