Submission #923465

#	Time	Username	Problem	Language	Result	Execution time	Memory
923465		Gromp15	Semiexpress (JOI17_semiexpress)	C++17	100 / 100	1 ms	460 KiB

semiexpress

#include <bits/stdc++.h>
#define ll long long
#define ar array
#define db double
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uniform_int_distribution<int>(l, r)(rng)
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
void test_case() {
	// for all station intervals (l, r)
	// there are r-l-1 potential spots that we can get
	// it costs B for a semiexp train
	// find the last one s.t. local train does not reach
	// greedily choose the semiexp trains that would allow the most number of stations to be reached in T stops
	int n, m, k, a, b, c;
	cin >> n >> m >> k >> a >> c >> b;
	ll T; cin >> T;
	vector<int> stations(m);
	for (int &x : stations) cin >> x;
	k -= m;
	int ans = 0;
	for (int i = 1; i < m; i++) ans += (ll)(stations[i] - 1) * c <= T;
	auto cost = [&](int pos) {
		auto it = lower_bound(all(stations), pos);
		assert(it != stations.begin());
		int where = *prev(it);
		return (ll)(where - 1) * c + (ll)(pos - where) * b;
	};
	auto calc = [&](int l, int r) -> int { // how many stations we can get if we build one at l
		ll C = cost(l);
		if (C > T) return 0;
		return 1 + min((T - C) / a, (ll)(r - l));
	};
	priority_queue<ar<int, 3>> q;
	for (int i = 0; i < m-1; i++) {
		int l = stations[i], r = stations[i+1];
		if (l+1 == r) continue;
		auto good = [&](int pos) {
			return (ll)(pos - l) * a + (ll)c * (l - 1) <= T;
		};
		int L = l+1, R = r-1;
		if (good(L)) {
			int cur = L, bl = L, br = R;
			while (bl <= br) {
				int mid = (bl+br)/2;
				if (good(mid)) cur = mid, bl = mid+1;
				else br = mid-1;
			}
			ans += cur - l;
			if (cur+1 <= R) {
				q.push({calc(cur+1, R), cur+1, R});
			}
		}
		else q.push({calc(L, R), L, R});
	}
	while (k-- && q.size()) {
		auto [get, l, r] = q.top();
		q.pop();
		ans += get;
		if (l + get <= r) {
			q.push({calc(l+get, r), l+get, r});
		}
	}
	cout << ans << '\n';



}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 52 / 52