Submission #697093

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
697093	2023-02-08T08:22:26 Z	amunduzbaev	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2000 ms	29460 KB

coach

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;
#define int ll

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int X, n, m, w, t; cin >> X >> n >> m >> w >> t;
	vector<int> s(n), d(m), c(m);
	vector<ar<int, 2>> a;
	for(int i=0;i<n;i++){
		cin >> s[i];
		a.push_back({s[i] % t, -s[i]});
	}
	for(int i=0;i<m;i++){
		cin >> d[i] >> c[i];
		a.push_back({d[i], c[i]});
	}
	a.push_back({X % t, -X});
	a.push_back({0, 0});
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
	int sz = a.size();
	vector<int> pref(sz), cnt(sz), tot(sz);
	for(int i=1;i<sz;i++){
		pref[i] = pref[i-1], cnt[i] = cnt[i-1];
		if(a[i][1] > 0){
			tot[i] = X / t + (a[i][0] <= (X % t));
			pref[i] += a[i][1];
			cnt[i]++;
		}
	}
	
	vector<int> dp(sz);
	dp[0] = (X / t + 1) * w;
	for(int i=1;i<sz;i++){
		if(a[i][1] > 0){
			dp[i] = dp[i-1] + tot[i] * w;
			continue;
		}
		
		dp[i] = dp[i-1];
		int s = -a[i][1] / t;
		for(int j=0;j<i;j++){
			//~ cout<<j<<" "<<i<<" "<<dp[j]<<" "<<s * w * (cnt[i] - cnt[j])<<" "<<pref[i] - pref[j]<<"\n";
			dp[i] = min(dp[i], dp[j] + s * w * (cnt[i] - cnt[j]) + pref[i] - pref[j]);
		}
	}
	
	//~ for(int i=0;i<sz;i++){
		//~ cout<<dp[i]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<sz;i++){
		//~ cout<<a[i][0]<<" ";
	//~ } cout<<"\n";
	//~ for(int i=0;i<sz;i++){
		//~ cout<<a[i][1]<<" ";
	//~ } cout<<"\n";
	
	cout<<dp[sz - 1]<<"\n";
}

Subtask #1
16.0 / 16.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
0 / 29.0

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

Submission #697093

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