Submission #563869

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
563869	2022-05-18T07:43:28 Z	amunduzbaev	Long Distance Coach (JOI17_coach)	C++17	71 / 100	2000 ms	14284 KB

coach

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
#define int long long

const int inf = 1e18;
const int N = 2e5 + 5;
int s[N], d[N], c[N], pref[N], cnt[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int x, n, m, w, t; cin>>x>>n>>m>>w>>t;
	for(int i=0;i<n;i++) cin>>s[i];
	vector<int> p(m), d_(m), mn(m, x + 1);
	int tot = 0;
	for(int i=0;i<m;i++){
		cin>>d[i]>>c[i];
		p[i] = i;
	}
	
	tot += (x / t + 1) * w;
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return d[i] < d[j];
	});
	for(int i=0;i<m;i++){
		d_[i] = d[p[i]];
		cnt[i] = x / t + (d_[i] < x % t);
		tot += cnt[i] * w;
		if(i) pref[i] += pref[i-1], cnt[i] += cnt[i-1];
		pref[i] += c[p[i]];
	}
	s[n] = x;
	for(int i=0;i<=n;i++){
		int j = upper_bound(d_.begin(), d_.end(), s[i] % t) - d_.begin();
		if(j){ --j;
			//~ assert(d_[j] != s[i] % t);
			mn[j] = min(mn[j], s[i]);
		}
	}
	
	vector<int> dp(m);
	for(int i=0;i<m;i++){
		if(i) dp[i] = dp[i-1];
		if(mn[i] > x) continue;
		int M = mn[i] / t;
		for(int j=i-1;~j;j--){
			dp[i] = min(dp[i], dp[j] + cnt[j] * w - M * j * w - pref[j] - cnt[i] * w + M * i * w + pref[i]);
		}
		
		dp[i] = min(dp[i], -cnt[i] * w + M * (i + 1) * w + pref[i]);
	}
	
	//~ for(int i=0;i<m;i++) cout<<dp[i]<<" ";
	//~ cout<<"\n";
	
	//~ cout<<dp[m-1]<<"\n";
	cout<<tot + dp[m-1]<<"\n";
}

/*

166833333456456789
333333209997456789

*/

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	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 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	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 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	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 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	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 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	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 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	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 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	0 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	1 ms	340 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	0 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	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 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	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 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	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 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	0 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	1 ms	340 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	0 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	4 ms	468 KB	Output is correct
39	Correct	6 ms	468 KB	Output is correct
40	Correct	7 ms	468 KB	Output is correct
41	Correct	6 ms	468 KB	Output is correct
42	Correct	6 ms	468 KB	Output is correct
43	Correct	4 ms	492 KB	Output is correct
44	Correct	6 ms	496 KB	Output is correct
45	Correct	4 ms	468 KB	Output is correct
46	Correct	8 ms	468 KB	Output is correct
47	Correct	8 ms	468 KB	Output is correct
48	Correct	5 ms	500 KB	Output is correct
49	Correct	4 ms	468 KB	Output is correct
50	Correct	4 ms	468 KB	Output is correct
51	Correct	4 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	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 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	1 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	1 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	0 ms	340 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	1 ms	340 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Correct	1 ms	340 KB	Output is correct
24	Correct	1 ms	340 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 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	0 ms	340 KB	Output is correct
30	Correct	0 ms	340 KB	Output is correct
31	Correct	1 ms	340 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	0 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	4 ms	468 KB	Output is correct
39	Correct	6 ms	468 KB	Output is correct
40	Correct	7 ms	468 KB	Output is correct
41	Correct	6 ms	468 KB	Output is correct
42	Correct	6 ms	468 KB	Output is correct
43	Correct	4 ms	492 KB	Output is correct
44	Correct	6 ms	496 KB	Output is correct
45	Correct	4 ms	468 KB	Output is correct
46	Correct	8 ms	468 KB	Output is correct
47	Correct	8 ms	468 KB	Output is correct
48	Correct	5 ms	500 KB	Output is correct
49	Correct	4 ms	468 KB	Output is correct
50	Correct	4 ms	468 KB	Output is correct
51	Correct	4 ms	468 KB	Output is correct
52	Execution timed out	2084 ms	14284 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

Submission #563869

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