Submission #74566

#	Time	Username	Problem	Language	Result	Execution time	Memory
74566		shoemakerjo	Semiexpress (JOI17_semiexpress)	C++14	100 / 100	3 ms	1000 KiB

semiexpress

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define maxn 3010
#define pii pair<ll, ll>
#define pil pair<ll, ll>
#define mp make_pair

ll ans = 0;
ll stops[maxn];
ll N;
int M, K;
ll A, B, C, T;
priority_queue< pair< pil, pii > > pq;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M >> K;
	cin >> A >> B >> C >> T;
	for (int i = 0; i < M; i++) {
		cin >> stops[i];
	}
	for (int i = 0; i < M-1; i++) {
		if (B*(stops[i]-1) <= T) ans++;
		else continue;
		ll numnx = (T - B*(stops[i]-1))/A;
		if (numnx >= stops[i+1]-stops[i]-1) {
			ans += stops[i+1]-stops[i]-1;

			// cout << "ans after " << stops[i] << ": " << ans << endl;
			continue;
		}
		ans += numnx;
		// cout << "ans after " << stops[i] << ": " << ans << endl;


		ll nxstop = stops[i] + numnx+1;
		if (nxstop == stops[i+1]) continue;
		ll ttaken = B*(stops[i] - 1) + C*(nxstop - stops[i]);
		if (ttaken > T) continue;
		ll nguys = (T-ttaken)/A;

		nguys = min(nguys, stops[i+1]-nxstop-1LL);
		ll ng = nguys+1; //because of first

		// cout << "      " <<  stops[i] << " adds " << ng << ", " <<
			 // ttaken << ", " << nxstop << ", " << stops[i+1] << endl;
		pq.push(mp( mp(ng, ttaken), mp(nxstop, stops[i+1]) ));
		
	}

	// cout << "ans before adding:  " << ans << endl;

	for (int i = 0; i < K-M; i++) {
		if (pq.size() == 0) break;
		pair<pil, pii> cur = pq.top(); pq.pop();

		ll numadd = cur.first.first;
		ll ctime = cur.first.second;
		ll cstop = cur.second.first;
		ll backend = cur.second.second;

		ans += numadd;
		ll nxstop = cstop + numadd;
		if (nxstop == backend) continue;

		ctime += C * (nxstop - cstop);
		if (ctime > T) continue;
		ll nguys = (T-ctime)/A;

		nguys = min(nguys, backend-nxstop-1LL);
		ll ng = nguys+1;

		// cout << "      another add: " << ng << ", " << ctime << 
		// 	", " << nxstop << ", " << backend << endl;
		pq.push(mp( mp(ng, ctime), mp(nxstop, backend)));

	}

	if (B*(N-1) <= T) {
		ans++;
	}
	cout << ans-1 << endl; //i think i count 0
}

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