#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
#define l first
#define r second
typedef long long lint;
typedef pair<lint,lint> ii;
const lint inf = 1e17;
lint n, K, TT, T;
lint pos[100005];
ii memo[1005][1005];
ii dp(int l, int r){
if(r < K) return ii(inf,-inf);
if(l > K) return ii(inf,-inf);
if(l == K and r == K) return ii(pos[K], pos[K]);
if(memo[l][r] != ii(-1,-1)) return memo[l][r];
lint dis = r-l;
ii A = dp(l, r-1);
A.l -= T, A.r += T;
ii B = ii(pos[r] - dis*T, pos[r] + dis*T);
ii res1 = ii(max(A.l, B.l), min(A.r, B.r));
if(res1.l > res1.r) res1 = ii(inf,-inf);
A = dp(l+1,r);
A.l -= T, A.r += T;
B = ii(pos[l] - dis*T, pos[l] + dis*T);
ii res2 = ii(max(A.l, B.l), min(A.r, B.r));
if(res2.l > res2.r) res2 = ii(inf,-inf);
//show2(l,r);
//show2(res1.l, res1.r);
//show2(res2.l, res2.r);
if(res1.l > res2.l) swap(res1, res2);
if(res2.l <= 1e15 and res1.r >= -1e15) assert(res2.l <= res1.r + 1);
ii newres = ii(min(res1.l,res2.l), max(res1.r,res2.r));
if(newres.l > newres.r) newres = ii(inf,-inf);
memo[l][r] = newres;
//show2(newres.l, newres.r);
return newres;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> K >> TT; K--;
for(int i = 0;i < n;i++) cin >> pos[i];
lint low = -1, high = 1e10 / TT;
while(low != high-1){
lint mid = (low+high)/2;
T = mid * TT;
for(int i = 0;i < n;i++) fill(memo[i], memo[i]+n, ii(-1,-1));
ii res = dp(0,n-1);
if(res.l <= res.r) high = mid;
else low = mid;
}
cout << high;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
120 ms |
11596 KB |
Output is correct |
23 |
Correct |
66 ms |
7680 KB |
Output is correct |
24 |
Correct |
79 ms |
11596 KB |
Output is correct |
25 |
Correct |
104 ms |
16128 KB |
Output is correct |
26 |
Correct |
155 ms |
16144 KB |
Output is correct |
27 |
Correct |
166 ms |
16144 KB |
Output is correct |
28 |
Correct |
265 ms |
16032 KB |
Output is correct |
29 |
Correct |
262 ms |
16132 KB |
Output is correct |
30 |
Correct |
266 ms |
16140 KB |
Output is correct |
31 |
Correct |
276 ms |
16132 KB |
Output is correct |
32 |
Correct |
292 ms |
16128 KB |
Output is correct |
33 |
Correct |
256 ms |
16076 KB |
Output is correct |
34 |
Correct |
197 ms |
16076 KB |
Output is correct |
35 |
Correct |
280 ms |
16076 KB |
Output is correct |
36 |
Correct |
122 ms |
16136 KB |
Output is correct |
37 |
Correct |
129 ms |
16076 KB |
Output is correct |
38 |
Correct |
303 ms |
16076 KB |
Output is correct |
39 |
Correct |
129 ms |
16132 KB |
Output is correct |
40 |
Correct |
242 ms |
16124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
120 ms |
11596 KB |
Output is correct |
23 |
Correct |
66 ms |
7680 KB |
Output is correct |
24 |
Correct |
79 ms |
11596 KB |
Output is correct |
25 |
Correct |
104 ms |
16128 KB |
Output is correct |
26 |
Correct |
155 ms |
16144 KB |
Output is correct |
27 |
Correct |
166 ms |
16144 KB |
Output is correct |
28 |
Correct |
265 ms |
16032 KB |
Output is correct |
29 |
Correct |
262 ms |
16132 KB |
Output is correct |
30 |
Correct |
266 ms |
16140 KB |
Output is correct |
31 |
Correct |
276 ms |
16132 KB |
Output is correct |
32 |
Correct |
292 ms |
16128 KB |
Output is correct |
33 |
Correct |
256 ms |
16076 KB |
Output is correct |
34 |
Correct |
197 ms |
16076 KB |
Output is correct |
35 |
Correct |
280 ms |
16076 KB |
Output is correct |
36 |
Correct |
122 ms |
16136 KB |
Output is correct |
37 |
Correct |
129 ms |
16076 KB |
Output is correct |
38 |
Correct |
303 ms |
16076 KB |
Output is correct |
39 |
Correct |
129 ms |
16132 KB |
Output is correct |
40 |
Correct |
242 ms |
16124 KB |
Output is correct |
41 |
Runtime error |
99 ms |
34740 KB |
Execution killed with signal 11 |
42 |
Halted |
0 ms |
0 KB |
- |