Submission #63319

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
63319	2018-08-01T11:37:43 Z	zadrga	Long Distance Coach (JOI17_coach)	C++14	71 / 100	11 ms	1888 KB

coach

// 13.23

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 2111

typedef long long ll;

ll dp[maxn], s[maxn], c[maxn], d[maxn];
pair<ll, ll> p[maxn];
vector<int> v[maxn];

 
int main(){
	ll x, n, m, w, t;
	scanf("%lld%lld%lld%lld%lld", &x, &n, &m, &w, &t);
	for(int i = 1; i <= n; i++)
		scanf("%lld", s + i);

	s[n + 1] = x;

	for(int i = 1; i <= m; i++)
		scanf("%lld%lld", &p[i].fi, &p[i].se);

	sort(p + 1, p + 1 + m);
	for(int i = 1; i <= m; i++){
		d[i] = p[i].fi;
		c[i] = p[i].se;
	}

	for(int i = 1; i <= n + 1; i++){
		int pos = lower_bound(d + 1, d + 1 + m, s[i] % t) - d - 1;
		v[pos].pb(i);
	}

	dp[0] = s[n + 1] / t * w + w;
	for(int i = 1; i <= m; i++){
		dp[i] = dp[i - 1] + (s[n + 1] - d[i]) / t * w + w;
		for(int pos : v[i]){
			ll cur = s[pos] / t;
			ll cost = 0;
			for(int j = i; j >= 1; j--){
				cost += c[j];
				dp[i] = min(dp[i], dp[j - 1] + cost + (i - j + 1) * cur * w);
			}	
		}
	}

	printf("%lld\n", dp[m]);
	return 0;
}

Compilation message

coach.cpp: In function 'int main()':
coach.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld%lld%lld", &x, &n, &m, &w, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
coach.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", s + i);
   ~~~~~^~~~~~~~~~~~~~~
coach.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld", &p[i].fi, &p[i].se);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	660 KB	Output is correct
4	Correct	3 ms	660 KB	Output is correct
5	Correct	4 ms	660 KB	Output is correct
6	Correct	2 ms	824 KB	Output is correct
7	Correct	3 ms	824 KB	Output is correct
8	Correct	3 ms	832 KB	Output is correct
9	Correct	3 ms	832 KB	Output is correct
10	Correct	4 ms	832 KB	Output is correct
11	Correct	2 ms	832 KB	Output is correct
12	Correct	2 ms	832 KB	Output is correct
13	Correct	3 ms	832 KB	Output is correct
14	Correct	3 ms	836 KB	Output is correct
15	Correct	2 ms	840 KB	Output is correct
16	Correct	2 ms	844 KB	Output is correct
17	Correct	3 ms	848 KB	Output is correct
18	Correct	2 ms	852 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	864 KB	Output is correct
21	Correct	3 ms	864 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct

Subtask #2
30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	660 KB	Output is correct
4	Correct	3 ms	660 KB	Output is correct
5	Correct	4 ms	660 KB	Output is correct
6	Correct	2 ms	824 KB	Output is correct
7	Correct	3 ms	824 KB	Output is correct
8	Correct	3 ms	832 KB	Output is correct
9	Correct	3 ms	832 KB	Output is correct
10	Correct	4 ms	832 KB	Output is correct
11	Correct	2 ms	832 KB	Output is correct
12	Correct	2 ms	832 KB	Output is correct
13	Correct	3 ms	832 KB	Output is correct
14	Correct	3 ms	836 KB	Output is correct
15	Correct	2 ms	840 KB	Output is correct
16	Correct	2 ms	844 KB	Output is correct
17	Correct	3 ms	848 KB	Output is correct
18	Correct	2 ms	852 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	864 KB	Output is correct
21	Correct	3 ms	864 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	872 KB	Output is correct
24	Correct	3 ms	880 KB	Output is correct
25	Correct	4 ms	928 KB	Output is correct
26	Correct	3 ms	928 KB	Output is correct
27	Correct	2 ms	928 KB	Output is correct
28	Correct	3 ms	928 KB	Output is correct
29	Correct	2 ms	928 KB	Output is correct
30	Correct	2 ms	928 KB	Output is correct
31	Correct	3 ms	928 KB	Output is correct
32	Correct	2 ms	960 KB	Output is correct
33	Correct	3 ms	1044 KB	Output is correct
34	Correct	3 ms	1044 KB	Output is correct
35	Correct	3 ms	1044 KB	Output is correct
36	Correct	3 ms	1044 KB	Output is correct
37	Correct	3 ms	1044 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	660 KB	Output is correct
4	Correct	3 ms	660 KB	Output is correct
5	Correct	4 ms	660 KB	Output is correct
6	Correct	2 ms	824 KB	Output is correct
7	Correct	3 ms	824 KB	Output is correct
8	Correct	3 ms	832 KB	Output is correct
9	Correct	3 ms	832 KB	Output is correct
10	Correct	4 ms	832 KB	Output is correct
11	Correct	2 ms	832 KB	Output is correct
12	Correct	2 ms	832 KB	Output is correct
13	Correct	3 ms	832 KB	Output is correct
14	Correct	3 ms	836 KB	Output is correct
15	Correct	2 ms	840 KB	Output is correct
16	Correct	2 ms	844 KB	Output is correct
17	Correct	3 ms	848 KB	Output is correct
18	Correct	2 ms	852 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	864 KB	Output is correct
21	Correct	3 ms	864 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	872 KB	Output is correct
24	Correct	3 ms	880 KB	Output is correct
25	Correct	4 ms	928 KB	Output is correct
26	Correct	3 ms	928 KB	Output is correct
27	Correct	2 ms	928 KB	Output is correct
28	Correct	3 ms	928 KB	Output is correct
29	Correct	2 ms	928 KB	Output is correct
30	Correct	2 ms	928 KB	Output is correct
31	Correct	3 ms	928 KB	Output is correct
32	Correct	2 ms	960 KB	Output is correct
33	Correct	3 ms	1044 KB	Output is correct
34	Correct	3 ms	1044 KB	Output is correct
35	Correct	3 ms	1044 KB	Output is correct
36	Correct	3 ms	1044 KB	Output is correct
37	Correct	3 ms	1044 KB	Output is correct
38	Correct	7 ms	1064 KB	Output is correct
39	Correct	8 ms	1236 KB	Output is correct
40	Correct	9 ms	1296 KB	Output is correct
41	Correct	8 ms	1296 KB	Output is correct
42	Correct	9 ms	1296 KB	Output is correct
43	Correct	7 ms	1320 KB	Output is correct
44	Correct	8 ms	1372 KB	Output is correct
45	Correct	7 ms	1552 KB	Output is correct
46	Correct	10 ms	1552 KB	Output is correct
47	Correct	8 ms	1588 KB	Output is correct
48	Correct	11 ms	1644 KB	Output is correct
49	Correct	7 ms	1644 KB	Output is correct
50	Correct	7 ms	1664 KB	Output is correct
51	Correct	10 ms	1704 KB	Output is correct

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	632 KB	Output is correct
2	Correct	3 ms	632 KB	Output is correct
3	Correct	3 ms	660 KB	Output is correct
4	Correct	3 ms	660 KB	Output is correct
5	Correct	4 ms	660 KB	Output is correct
6	Correct	2 ms	824 KB	Output is correct
7	Correct	3 ms	824 KB	Output is correct
8	Correct	3 ms	832 KB	Output is correct
9	Correct	3 ms	832 KB	Output is correct
10	Correct	4 ms	832 KB	Output is correct
11	Correct	2 ms	832 KB	Output is correct
12	Correct	2 ms	832 KB	Output is correct
13	Correct	3 ms	832 KB	Output is correct
14	Correct	3 ms	836 KB	Output is correct
15	Correct	2 ms	840 KB	Output is correct
16	Correct	2 ms	844 KB	Output is correct
17	Correct	3 ms	848 KB	Output is correct
18	Correct	2 ms	852 KB	Output is correct
19	Correct	3 ms	856 KB	Output is correct
20	Correct	3 ms	864 KB	Output is correct
21	Correct	3 ms	864 KB	Output is correct
22	Correct	3 ms	868 KB	Output is correct
23	Correct	3 ms	872 KB	Output is correct
24	Correct	3 ms	880 KB	Output is correct
25	Correct	4 ms	928 KB	Output is correct
26	Correct	3 ms	928 KB	Output is correct
27	Correct	2 ms	928 KB	Output is correct
28	Correct	3 ms	928 KB	Output is correct
29	Correct	2 ms	928 KB	Output is correct
30	Correct	2 ms	928 KB	Output is correct
31	Correct	3 ms	928 KB	Output is correct
32	Correct	2 ms	960 KB	Output is correct
33	Correct	3 ms	1044 KB	Output is correct
34	Correct	3 ms	1044 KB	Output is correct
35	Correct	3 ms	1044 KB	Output is correct
36	Correct	3 ms	1044 KB	Output is correct
37	Correct	3 ms	1044 KB	Output is correct
38	Correct	7 ms	1064 KB	Output is correct
39	Correct	8 ms	1236 KB	Output is correct
40	Correct	9 ms	1296 KB	Output is correct
41	Correct	8 ms	1296 KB	Output is correct
42	Correct	9 ms	1296 KB	Output is correct
43	Correct	7 ms	1320 KB	Output is correct
44	Correct	8 ms	1372 KB	Output is correct
45	Correct	7 ms	1552 KB	Output is correct
46	Correct	10 ms	1552 KB	Output is correct
47	Correct	8 ms	1588 KB	Output is correct
48	Correct	11 ms	1644 KB	Output is correct
49	Correct	7 ms	1644 KB	Output is correct
50	Correct	7 ms	1664 KB	Output is correct
51	Correct	10 ms	1704 KB	Output is correct
52	Execution timed out	7 ms	1888 KB	Time limit exceeded (wall clock)
53	Halted	0 ms	0 KB	-

Submission #63319

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