#include "overtaking.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
vector<vector<pair<ll, ll>>> dp;
vector<vector<ll>> esim;
vector<ll> t, w, s;
ll n, x, l, m;
bool cmp(pair<ll, ll> x, pair<ll, ll> y) {
if (x.first != y.first) return x.first < y.first;
if (w[x.second] != w[y.second]) return w[x.second] < w[y.second];
return x.second < y.second;
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
t.clear();
w.clear();
s.clear();
esim.clear();
dp.clear();
m = M;
l = L;
x = X;
n = 0;
for (auto& it : S) {
s.push_back(it);
}
for (ll i = 0; i < N; i++) {
if (W[i] > x) {
t.push_back(T[i]);
w.push_back(W[i]);
n++;
}
}
dp.resize(m);
esim.resize(m);
for (ll i = 0; i < n; i++) {
dp[0].push_back({ t[i], i });
}
sort(dp[0].begin(), dp[0].end(), cmp);
for (ll j = 1; j < m; j++) {
ll cur_mx = 0;
for (auto& it : dp[j - 1]) {
cur_mx = max(cur_mx, it.first + w[it.second] * 1ll * (s[j] - s[j - 1]));
dp[j].push_back({ cur_mx, it.second });
}
sort(dp[j].begin(), dp[j].end(), cmp);
map<ll, ll> mp;
for (auto& it : dp[j]) {
mp[it.second] = it.first;
}
cur_mx = 0;
for (auto& it : dp[j - 1]) {
cur_mx = max(cur_mx, mp[it.second]);
esim[j].push_back(cur_mx);
}
}
}
ll arrival_time(ll Y) {
ll cur_ind = 0;
for (auto& it : t) {
if (it < Y) cur_ind++;
}
if (cur_ind == 0) {
return l * 1ll * x + Y;
}
ll time = Y;
for (ll i = 1; i < m; i++) {
time = max(time + (s[i] - s[i - 1]) * 1ll * x, esim[i][cur_ind - 1]);
while (cur_ind > 0 && dp[i][cur_ind - 1].first >= time) {
cur_ind--;
}
if (cur_ind == 0) {
return (l - s[i]) * 1ll * x + time;
}
}
return time;
}
/*
int main() {
int L, N, X, M, Q;
cin >> L >> N >> X >> M >> Q;
vector <ll> T(N);
vector <int> W(N), S(M);
for (auto &it : T) {
cin >> it;
}
for (auto& it : W) {
cin >> it;
}
for (auto& it : S) {
cin >> it;
}
init(L, N, T, W, X, M, S);
while (Q--) {
ll k;
cin >> k;
cout << arrival_time(k) << "\n";
}
}*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
600 KB |
Output is correct |
10 |
Correct |
2 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
2 ms |
604 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
2 ms |
860 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
2 ms |
604 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
604 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
436 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
2 ms |
600 KB |
Output is correct |
34 |
Correct |
2 ms |
604 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
1 ms |
604 KB |
Output is correct |
37 |
Correct |
2 ms |
604 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
344 KB |
Output is correct |
40 |
Correct |
1 ms |
692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
600 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
2 ms |
604 KB |
Output is correct |
17 |
Correct |
1 ms |
600 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
860 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
2 ms |
604 KB |
Output is correct |
23 |
Correct |
2 ms |
604 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
2 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
2 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
604 KB |
Output is correct |
34 |
Correct |
2 ms |
604 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
1 ms |
436 KB |
Output is correct |
37 |
Correct |
1 ms |
604 KB |
Output is correct |
38 |
Correct |
1 ms |
604 KB |
Output is correct |
39 |
Correct |
1 ms |
604 KB |
Output is correct |
40 |
Correct |
2 ms |
600 KB |
Output is correct |
41 |
Correct |
2 ms |
604 KB |
Output is correct |
42 |
Correct |
1 ms |
604 KB |
Output is correct |
43 |
Correct |
1 ms |
604 KB |
Output is correct |
44 |
Correct |
2 ms |
604 KB |
Output is correct |
45 |
Correct |
0 ms |
348 KB |
Output is correct |
46 |
Correct |
0 ms |
344 KB |
Output is correct |
47 |
Correct |
1 ms |
692 KB |
Output is correct |
48 |
Correct |
195 ms |
24520 KB |
Output is correct |
49 |
Correct |
199 ms |
24656 KB |
Output is correct |
50 |
Correct |
197 ms |
24664 KB |
Output is correct |
51 |
Correct |
195 ms |
24664 KB |
Output is correct |
52 |
Correct |
198 ms |
24832 KB |
Output is correct |
53 |
Correct |
205 ms |
24664 KB |
Output is correct |
54 |
Correct |
195 ms |
24748 KB |
Output is correct |
55 |
Correct |
205 ms |
24676 KB |
Output is correct |
56 |
Correct |
197 ms |
24660 KB |
Output is correct |
57 |
Correct |
190 ms |
24660 KB |
Output is correct |
58 |
Correct |
194 ms |
24796 KB |
Output is correct |
59 |
Correct |
192 ms |
24660 KB |
Output is correct |
60 |
Correct |
193 ms |
24776 KB |
Output is correct |
61 |
Correct |
200 ms |
24660 KB |
Output is correct |
62 |
Correct |
6 ms |
600 KB |
Output is correct |
63 |
Correct |
5 ms |
604 KB |
Output is correct |
64 |
Correct |
106 ms |
12556 KB |
Output is correct |
65 |
Correct |
119 ms |
12624 KB |
Output is correct |
66 |
Correct |
222 ms |
24656 KB |
Output is correct |
67 |
Correct |
235 ms |
24660 KB |
Output is correct |
68 |
Correct |
228 ms |
25116 KB |
Output is correct |
69 |
Correct |
185 ms |
24656 KB |
Output is correct |
70 |
Correct |
190 ms |
24776 KB |
Output is correct |
71 |
Correct |
196 ms |
24916 KB |
Output is correct |
72 |
Correct |
197 ms |
24660 KB |
Output is correct |
73 |
Correct |
193 ms |
24660 KB |
Output is correct |
74 |
Correct |
200 ms |
24632 KB |
Output is correct |
75 |
Correct |
2 ms |
604 KB |
Output is correct |
76 |
Correct |
1 ms |
860 KB |
Output is correct |
77 |
Correct |
1 ms |
604 KB |
Output is correct |
78 |
Correct |
174 ms |
24660 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
604 KB |
Output is correct |
10 |
Correct |
2 ms |
600 KB |
Output is correct |
11 |
Correct |
2 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
348 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
2 ms |
604 KB |
Output is correct |
20 |
Correct |
2 ms |
604 KB |
Output is correct |
21 |
Correct |
2 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
348 KB |
Output is correct |
23 |
Correct |
2 ms |
604 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
348 KB |
Output is correct |
26 |
Correct |
1 ms |
348 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
2 ms |
860 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
2 ms |
604 KB |
Output is correct |
34 |
Correct |
2 ms |
604 KB |
Output is correct |
35 |
Correct |
1 ms |
604 KB |
Output is correct |
36 |
Correct |
1 ms |
604 KB |
Output is correct |
37 |
Correct |
2 ms |
604 KB |
Output is correct |
38 |
Correct |
1 ms |
604 KB |
Output is correct |
39 |
Correct |
1 ms |
604 KB |
Output is correct |
40 |
Correct |
1 ms |
604 KB |
Output is correct |
41 |
Correct |
1 ms |
604 KB |
Output is correct |
42 |
Correct |
2 ms |
604 KB |
Output is correct |
43 |
Correct |
1 ms |
604 KB |
Output is correct |
44 |
Correct |
1 ms |
604 KB |
Output is correct |
45 |
Correct |
2 ms |
604 KB |
Output is correct |
46 |
Correct |
1 ms |
604 KB |
Output is correct |
47 |
Correct |
1 ms |
436 KB |
Output is correct |
48 |
Correct |
1 ms |
604 KB |
Output is correct |
49 |
Correct |
1 ms |
604 KB |
Output is correct |
50 |
Correct |
1 ms |
604 KB |
Output is correct |
51 |
Correct |
2 ms |
600 KB |
Output is correct |
52 |
Correct |
2 ms |
604 KB |
Output is correct |
53 |
Correct |
1 ms |
604 KB |
Output is correct |
54 |
Correct |
1 ms |
604 KB |
Output is correct |
55 |
Correct |
2 ms |
604 KB |
Output is correct |
56 |
Correct |
0 ms |
348 KB |
Output is correct |
57 |
Correct |
0 ms |
344 KB |
Output is correct |
58 |
Correct |
1 ms |
692 KB |
Output is correct |
59 |
Correct |
195 ms |
24520 KB |
Output is correct |
60 |
Correct |
199 ms |
24656 KB |
Output is correct |
61 |
Correct |
197 ms |
24664 KB |
Output is correct |
62 |
Correct |
195 ms |
24664 KB |
Output is correct |
63 |
Correct |
198 ms |
24832 KB |
Output is correct |
64 |
Correct |
205 ms |
24664 KB |
Output is correct |
65 |
Correct |
195 ms |
24748 KB |
Output is correct |
66 |
Correct |
205 ms |
24676 KB |
Output is correct |
67 |
Correct |
197 ms |
24660 KB |
Output is correct |
68 |
Correct |
190 ms |
24660 KB |
Output is correct |
69 |
Correct |
194 ms |
24796 KB |
Output is correct |
70 |
Correct |
192 ms |
24660 KB |
Output is correct |
71 |
Correct |
193 ms |
24776 KB |
Output is correct |
72 |
Correct |
200 ms |
24660 KB |
Output is correct |
73 |
Correct |
6 ms |
600 KB |
Output is correct |
74 |
Correct |
5 ms |
604 KB |
Output is correct |
75 |
Correct |
106 ms |
12556 KB |
Output is correct |
76 |
Correct |
119 ms |
12624 KB |
Output is correct |
77 |
Correct |
222 ms |
24656 KB |
Output is correct |
78 |
Correct |
235 ms |
24660 KB |
Output is correct |
79 |
Correct |
228 ms |
25116 KB |
Output is correct |
80 |
Correct |
185 ms |
24656 KB |
Output is correct |
81 |
Correct |
190 ms |
24776 KB |
Output is correct |
82 |
Correct |
196 ms |
24916 KB |
Output is correct |
83 |
Correct |
197 ms |
24660 KB |
Output is correct |
84 |
Correct |
193 ms |
24660 KB |
Output is correct |
85 |
Correct |
200 ms |
24632 KB |
Output is correct |
86 |
Correct |
2 ms |
604 KB |
Output is correct |
87 |
Correct |
1 ms |
860 KB |
Output is correct |
88 |
Correct |
1 ms |
604 KB |
Output is correct |
89 |
Correct |
174 ms |
24660 KB |
Output is correct |
90 |
Correct |
994 ms |
27656 KB |
Output is correct |
91 |
Execution timed out |
3522 ms |
49744 KB |
Time limit exceeded |
92 |
Halted |
0 ms |
0 KB |
- |