Submission #821620

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
821620	2023-08-11T12:09:02 Z	AdamGS	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2000 ms	11248 KB

coach

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=2e5+7;
ll T[LIM], dp[LIM], kiedy[LIM], pref[LIM], x, n, m, w, t, N=1;
pair<ll,ll>P[LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> x >> n >> m >> w >> t;
	rep(i, 40) N*=2;
	rep(i, n) cin >> T[i];
	T[n]=x; ++n;
	rep(i, m) cin >> P[i].st >> P[i].nd;
	sort(T, T+n);
	sort(P, P+m);
	rep(i, m) {
		kiedy[i]=INF;
		pref[i]=P[i].nd;
		if(i) pref[i]+=pref[i-1];
	}
	rep(i, n) {
		ll po=0, ko=m-1;
		while(po<ko) {
			ll sr=(po+ko+1)/2;
			if(P[sr].st>T[i]%t) ko=sr-1; else po=sr;
		}
		if(P[po].st>T[i]%t) continue;
		kiedy[po]=min(kiedy[po], T[i]/t);
	}
	rep(i, m) {
		ll ile=w*(x/t);
		if(x%t>P[i].st) ile+=w;
		dp[i]=ile;
		if(i) dp[i]+=dp[i-1];
		if(kiedy[i]!=INF) {
			for(ll j=0; j<i; ++j) {
				dp[i]=min(dp[i], pref[i]+i*kiedy[i]*w+dp[j]-pref[j]-j*w*kiedy[i]);
			}
			dp[i]=min(dp[i], pref[i]+(i+1)*kiedy[i]*w);
		}
	}
	cout << dp[m-1]+w*(x/t+1) << '\n';
}

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	292 KB	Output is correct

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	292 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	292 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	2 ms	468 KB	Output is correct
39	Correct	4 ms	468 KB	Output is correct
40	Correct	3 ms	468 KB	Output is correct
41	Correct	2 ms	392 KB	Output is correct
42	Correct	3 ms	432 KB	Output is correct
43	Correct	3 ms	468 KB	Output is correct
44	Correct	3 ms	468 KB	Output is correct
45	Correct	3 ms	468 KB	Output is correct
46	Correct	5 ms	468 KB	Output is correct
47	Correct	6 ms	468 KB	Output is correct
48	Correct	4 ms	468 KB	Output is correct
49	Correct	2 ms	464 KB	Output is correct
50	Correct	2 ms	468 KB	Output is correct
51	Correct	2 ms	468 KB	Output is correct

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	0 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	1 ms	340 KB	Output is correct
20	Correct	0 ms	340 KB	Output is correct
21	Correct	0 ms	340 KB	Output is correct
22	Correct	0 ms	292 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	0 ms	340 KB	Output is correct
26	Correct	0 ms	340 KB	Output is correct
27	Correct	1 ms	340 KB	Output is correct
28	Correct	0 ms	340 KB	Output is correct
29	Correct	1 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	1 ms	324 KB	Output is correct
32	Correct	0 ms	340 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	1 ms	340 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	1 ms	340 KB	Output is correct
37	Correct	1 ms	340 KB	Output is correct
38	Correct	2 ms	468 KB	Output is correct
39	Correct	4 ms	468 KB	Output is correct
40	Correct	3 ms	468 KB	Output is correct
41	Correct	2 ms	392 KB	Output is correct
42	Correct	3 ms	432 KB	Output is correct
43	Correct	3 ms	468 KB	Output is correct
44	Correct	3 ms	468 KB	Output is correct
45	Correct	3 ms	468 KB	Output is correct
46	Correct	5 ms	468 KB	Output is correct
47	Correct	6 ms	468 KB	Output is correct
48	Correct	4 ms	468 KB	Output is correct
49	Correct	2 ms	464 KB	Output is correct
50	Correct	2 ms	468 KB	Output is correct
51	Correct	2 ms	468 KB	Output is correct
52	Execution timed out	2066 ms	11248 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

Submission #821620

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 30.0 / 30.0

Subtask #3 25.0 / 25.0

Subtask #4 0 / 29.0

Subtask #1
16.0 / 16.0

Subtask #2
30.0 / 30.0

Subtask #3
25.0 / 25.0

Subtask #4
0 / 29.0