제출 #1180303

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180303		jbareja	Semiexpress (JOI17_semiexpress)	C++20	100 / 100	6 ms	4540 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

ll N; // liczba stacji lokalnego pociągu
ll M; // ekspresu
ll K; // semiekspresu

ll A; // czas przejazdu lokalnego pociągu między sąsiednimi stacjami
ll B; // ekspresu
ll C; // semiekspresu

ll T; // maksymalny czas podróży

vector<ll> S; // stacje ekspresu

ll ans = 0;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> K;
	cin >> A >> B >> C;
	cin >> T;

	ll new_semiexpress_stations = K - M;

	S.assign(M, 0);
	for (int i=0; i<M; i++) cin >> S[i];

	ll time = 0;

	priority_queue<ll> Q;

	for (int i=0; i<M; i++) {
		const ll last_express_station = S[max(0, i-1)];
		const ll express_station = S[i];
		time += (express_station - last_express_station) * B;
		// cout << "\nexpress_station = " << express_station << ", time = " << time << '\n';
		if (time > T) break;
		if (i != 0) ans++;
		if (i == M-1) break;
		const ll next_express_station = S[i+1];
		ll range = min(next_express_station - express_station - 1, (T - time) / A);
		// cout << "range = " << range << '\n';
		ans += range;
		ll time2 = time;
		ll pos = express_station;
		for (int j=0; j<new_semiexpress_stations; j++) {
			pos += range + 1;
			time2 += (range + 1) * C;
			if (pos >= next_express_station || time2 > T) break;
			// cout << "semiexpress_station = " << pos << ", time2 = " << time2 << '\n';
			range = min(next_express_station - pos - 1, (T - time2) / A);
			// cout << "range = " << range << '\n';
			// cout << "Q.push( " << range + 1 << " )\n";
			Q.push(range + 1);
		}
	}

	// cout << "ans = " << ans << ", Qsize = " << Q.size() << '\n';

	for (int i=0; i<new_semiexpress_stations; i++) {
		if (Q.empty()) break;
		ans += Q.top();
		Q.pop();
	}

	cout << ans << '\n';
}

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