#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
//讀: 5 想1~3: 8min 實作40min
int dp[205][205][2][205];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
memset(dp, -1, sizeof(dp));
int n, l;
cin >> n >> l;
vector<int>x(n+1), t(n+1);
x[0] = t[0] = 0;
for (int i = 1 ; i <= n ; i++) cin >> x[i];
for (int i = 1 ; i <= n ; i++) cin >> t[i];
dp[0][0][0][0] = dp[0][0][1][0] = 0;
n++;
int ans= 0;
for (int k = 0 ; k <= 200 ; k++) {//time
for (int i = 0 ; i < n ; i++) {//left
for (int j = n-1 ; j >= 0 ; j--) {//right
for (int p = 0 ; p <= 1 ; p++) {
if (dp[i][j][p][k] == -1) {
continue;
}
if ((i + 1) % n == j) {
//cout << i << " " << j << " " << p << " " << k << " " << dp[i][j][p][k] << "\n";
if (dp[i][j][p][k] > ans)ans = dp[i][j][p][k];
continue;
}
//cout << i << " " << j << " " << p << " " << k << " " << dp[i][j][p][k] << "\n";
//if (i + 1 == j) ans = max(ans, dp[i][j][p][k]);
int pos = (p == 0 ? x[i] : x[j]), next;
next = (i+1);
int cost = k + (x[next] - pos + l) % l;
dp[next][j][0][cost] = max(dp[next][j][0][cost], dp[i][j][p][k] + (cost <= t[next]));
/*if (dp[next][j][0][cost] > 0) {
cout << next << " " << j << " " << 0 << " " << cost << "\n";
return 0;
}*/
next = (j==0 ? n-1 : j-1);
cost = k + (pos - x[next] + l) % l;
dp[i][next][1][cost] = max(dp[i][next][1][cost], dp[i][j][p][k] + (cost <= t[next]));
/*if (dp[i][next][1][cost] > 0) {
cout << i << " " << next << " " << 1 << " " << cost << "\n";
return 0;
}*/
}
}
}
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
67828 KB |
Output is correct |
2 |
Correct |
9 ms |
67676 KB |
Output is correct |
3 |
Correct |
9 ms |
67800 KB |
Output is correct |
4 |
Correct |
8 ms |
67768 KB |
Output is correct |
5 |
Correct |
8 ms |
67676 KB |
Output is correct |
6 |
Correct |
9 ms |
67684 KB |
Output is correct |
7 |
Correct |
9 ms |
67680 KB |
Output is correct |
8 |
Correct |
9 ms |
67804 KB |
Output is correct |
9 |
Correct |
9 ms |
67904 KB |
Output is correct |
10 |
Correct |
8 ms |
67684 KB |
Output is correct |
11 |
Correct |
8 ms |
67744 KB |
Output is correct |
12 |
Correct |
9 ms |
67684 KB |
Output is correct |
13 |
Correct |
9 ms |
67688 KB |
Output is correct |
14 |
Correct |
10 ms |
67892 KB |
Output is correct |
15 |
Correct |
9 ms |
67688 KB |
Output is correct |
16 |
Correct |
9 ms |
67804 KB |
Output is correct |
17 |
Correct |
9 ms |
67940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
67828 KB |
Output is correct |
2 |
Correct |
9 ms |
67676 KB |
Output is correct |
3 |
Correct |
9 ms |
67800 KB |
Output is correct |
4 |
Correct |
8 ms |
67768 KB |
Output is correct |
5 |
Correct |
8 ms |
67676 KB |
Output is correct |
6 |
Correct |
9 ms |
67684 KB |
Output is correct |
7 |
Correct |
9 ms |
67680 KB |
Output is correct |
8 |
Correct |
9 ms |
67804 KB |
Output is correct |
9 |
Correct |
9 ms |
67904 KB |
Output is correct |
10 |
Correct |
8 ms |
67684 KB |
Output is correct |
11 |
Correct |
8 ms |
67744 KB |
Output is correct |
12 |
Correct |
9 ms |
67684 KB |
Output is correct |
13 |
Correct |
9 ms |
67688 KB |
Output is correct |
14 |
Correct |
10 ms |
67892 KB |
Output is correct |
15 |
Correct |
9 ms |
67688 KB |
Output is correct |
16 |
Correct |
9 ms |
67804 KB |
Output is correct |
17 |
Correct |
9 ms |
67940 KB |
Output is correct |
18 |
Incorrect |
9 ms |
67688 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
67828 KB |
Output is correct |
2 |
Correct |
9 ms |
67676 KB |
Output is correct |
3 |
Correct |
9 ms |
67800 KB |
Output is correct |
4 |
Correct |
8 ms |
67768 KB |
Output is correct |
5 |
Correct |
8 ms |
67676 KB |
Output is correct |
6 |
Correct |
9 ms |
67684 KB |
Output is correct |
7 |
Correct |
9 ms |
67680 KB |
Output is correct |
8 |
Correct |
9 ms |
67804 KB |
Output is correct |
9 |
Correct |
9 ms |
67904 KB |
Output is correct |
10 |
Correct |
8 ms |
67684 KB |
Output is correct |
11 |
Correct |
8 ms |
67744 KB |
Output is correct |
12 |
Correct |
9 ms |
67684 KB |
Output is correct |
13 |
Correct |
9 ms |
67688 KB |
Output is correct |
14 |
Correct |
10 ms |
67892 KB |
Output is correct |
15 |
Correct |
9 ms |
67688 KB |
Output is correct |
16 |
Correct |
9 ms |
67804 KB |
Output is correct |
17 |
Correct |
9 ms |
67940 KB |
Output is correct |
18 |
Correct |
97 ms |
67876 KB |
Output is correct |
19 |
Correct |
58 ms |
67896 KB |
Output is correct |
20 |
Correct |
35 ms |
67888 KB |
Output is correct |
21 |
Correct |
61 ms |
67932 KB |
Output is correct |
22 |
Correct |
68 ms |
67880 KB |
Output is correct |
23 |
Correct |
28 ms |
67684 KB |
Output is correct |
24 |
Correct |
23 ms |
67684 KB |
Output is correct |
25 |
Correct |
28 ms |
67936 KB |
Output is correct |
26 |
Correct |
14 ms |
67684 KB |
Output is correct |
27 |
Correct |
30 ms |
67684 KB |
Output is correct |
28 |
Correct |
22 ms |
67684 KB |
Output is correct |
29 |
Correct |
33 ms |
67896 KB |
Output is correct |
30 |
Correct |
24 ms |
67688 KB |
Output is correct |
31 |
Incorrect |
27 ms |
67684 KB |
Output isn't correct |
32 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
67828 KB |
Output is correct |
2 |
Correct |
9 ms |
67676 KB |
Output is correct |
3 |
Correct |
9 ms |
67800 KB |
Output is correct |
4 |
Correct |
8 ms |
67768 KB |
Output is correct |
5 |
Correct |
8 ms |
67676 KB |
Output is correct |
6 |
Correct |
9 ms |
67684 KB |
Output is correct |
7 |
Correct |
9 ms |
67680 KB |
Output is correct |
8 |
Correct |
9 ms |
67804 KB |
Output is correct |
9 |
Correct |
9 ms |
67904 KB |
Output is correct |
10 |
Correct |
8 ms |
67684 KB |
Output is correct |
11 |
Correct |
8 ms |
67744 KB |
Output is correct |
12 |
Correct |
9 ms |
67684 KB |
Output is correct |
13 |
Correct |
9 ms |
67688 KB |
Output is correct |
14 |
Correct |
10 ms |
67892 KB |
Output is correct |
15 |
Correct |
9 ms |
67688 KB |
Output is correct |
16 |
Correct |
9 ms |
67804 KB |
Output is correct |
17 |
Correct |
9 ms |
67940 KB |
Output is correct |
18 |
Incorrect |
9 ms |
67688 KB |
Output isn't correct |
19 |
Halted |
0 ms |
0 KB |
- |