oj.uz

Submission #74566

# Submission time Handle Problem Language Result Execution time Memory
74566 2018-09-03T19:47:12 Z shoemakerjo Semiexpress (JOI17_semiexpress) C++14
100 / 100
 3 ms 1000 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 536 KB Output is correct
11 Correct 2 ms 544 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 2 ms 552 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 768 KB Output is correct
18 Correct 2 ms 768 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 536 KB Output is correct
11 Correct 2 ms 544 KB Output is correct
12 Correct 2 ms 548 KB Output is correct
13 Correct 2 ms 552 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 624 KB Output is correct
16 Correct 2 ms 640 KB Output is correct
17 Correct 2 ms 768 KB Output is correct
18 Correct 2 ms 768 KB Output is correct
19 Correct 2 ms 768 KB Output is correct
20 Correct 2 ms 768 KB Output is correct
21 Correct 2 ms 768 KB Output is correct
22 Correct 2 ms 768 KB Output is correct
23 Correct 2 ms 876 KB Output is correct
24 Correct 2 ms 896 KB Output is correct
25 Correct 2 ms 896 KB Output is correct
26 Correct 2 ms 896 KB Output is correct
27 Correct 2 ms 984 KB Output is correct
28 Correct 3 ms 1000 KB Output is correct
29 Correct 2 ms 1000 KB Output is correct
30 Correct 2 ms 1000 KB Output is correct