Submission #539730

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
539730	2022-03-19T06:49:37 Z	cheissmart	Long Distance Coach (JOI17_coach)	C++14	71 / 100	2000 ms	15348 KB

coach

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;
const ll oo = 1e18;

signed main()
{
	IO_OP;

	ll x, t;
	int n, m, w;
	cin >> x >> n >> m >> w >> t;
	V<ll> s(n);
	for(int i = 0; i < n; i++)
		cin >> s[i];
	V<pair<ll, int>> a;
	for(int i = 0; i < m; i++) {
		ll d; int c;
		cin >> d >> c;
		a.EB(d, c);
	}
	sort(ALL(a));
	V<ll> aux(m, oo);
	s.PB(x);
	for(ll ss:s) {
		ll sa = ss / t, na = ss % t;
		int pos = int(upper_bound(ALL(a), MP(na, INF)) - a.begin());
		if(pos > 0)
			aux[pos - 1] = min(aux[pos - 1], sa);
	}
	V<ll> p(m + 1);
	for(int i = 0; i < m; i++)
		p[i + 1] = p[i] + a[i].S;
	V<ll> dp(m + 1);
	for(int i = 0; i <= m; i++) {
		if(i == 0) {
			dp[i] = 1LL * (x / t + 1) * w;
		} else {
			dp[i] = dp[i - 1] + 1LL * (x / t + 1 - (a[i - 1].F % t > x % t)) * w;
			if(aux[i - 1] != oo) for(int j = i - 1; j >= 0; j--) {
				dp[i] = min(dp[i], dp[j] + p[i] - p[j] + (i - j) * aux[i - 1] * w);
			}
		}		
	}
	cout << dp.back() << '\n';
}

Subtask #1
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 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	320 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	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	328 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	324 KB	Output is correct
19	Correct	1 ms	320 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 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	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 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	320 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	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	328 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	324 KB	Output is correct
19	Correct	1 ms	320 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 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	244 KB	Output is correct
25	Correct	1 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	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	324 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	324 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct

Subtask #3
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 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	320 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	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	328 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	324 KB	Output is correct
19	Correct	1 ms	320 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 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	244 KB	Output is correct
25	Correct	1 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	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	324 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	324 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	4 ms	468 KB	Output is correct
39	Correct	5 ms	468 KB	Output is correct
40	Correct	5 ms	468 KB	Output is correct
41	Correct	3 ms	468 KB	Output is correct
42	Correct	4 ms	464 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	380 KB	Output is correct
46	Correct	5 ms	372 KB	Output is correct
47	Correct	5 ms	472 KB	Output is correct
48	Correct	5 ms	468 KB	Output is correct
49	Correct	3 ms	468 KB	Output is correct
50	Correct	3 ms	468 KB	Output is correct
51	Correct	3 ms	468 KB	Output is correct

Subtask #4
0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 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	320 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	320 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	1 ms	328 KB	Output is correct
17	Correct	1 ms	212 KB	Output is correct
18	Correct	0 ms	324 KB	Output is correct
19	Correct	1 ms	320 KB	Output is correct
20	Correct	1 ms	212 KB	Output is correct
21	Correct	1 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	244 KB	Output is correct
25	Correct	1 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	212 KB	Output is correct
29	Correct	1 ms	212 KB	Output is correct
30	Correct	1 ms	212 KB	Output is correct
31	Correct	1 ms	212 KB	Output is correct
32	Correct	1 ms	324 KB	Output is correct
33	Correct	0 ms	212 KB	Output is correct
34	Correct	1 ms	212 KB	Output is correct
35	Correct	1 ms	324 KB	Output is correct
36	Correct	1 ms	212 KB	Output is correct
37	Correct	1 ms	212 KB	Output is correct
38	Correct	4 ms	468 KB	Output is correct
39	Correct	5 ms	468 KB	Output is correct
40	Correct	5 ms	468 KB	Output is correct
41	Correct	3 ms	468 KB	Output is correct
42	Correct	4 ms	464 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	380 KB	Output is correct
46	Correct	5 ms	372 KB	Output is correct
47	Correct	5 ms	472 KB	Output is correct
48	Correct	5 ms	468 KB	Output is correct
49	Correct	3 ms	468 KB	Output is correct
50	Correct	3 ms	468 KB	Output is correct
51	Correct	3 ms	468 KB	Output is correct
52	Execution timed out	2050 ms	15348 KB	Time limit exceeded
53	Halted	0 ms	0 KB	-

Submission #539730

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