#include <bits/stdc++.h>
#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
const int N = 16;
int dp[1<<N][N][N], x[N], t[N], ans = 0;
//mask, at, taken, dp[i][j][k] => time
signed main(){
fastio
int n,l;
cin >> n >> l;
for(int i = 0;i < n;i++){
cin >> x[i];
}
for(int i = 0;i < n;i++){
cin >> t[i];
}
for(int mask = 0;mask < (1<<n);mask++){
for(int i = 0;i < n;i++){
for(int j = 0;j <= n;j++){
dp[mask][i][j] = 1e18;
}
}
}
for(int i = 0;i < n;i++){
int tmp = min(x[i],(0-x[i]+l)%l);
int take = (tmp <= t[i]);
dp[(1<<i)][i][take] = tmp;
}
for(int mask = 0; mask < (1<<n); mask++){
for(int i = 0;i < n;i++){
if(mask&(1<<i)){
for(int j = 0;j < n;j++){
if(!(mask&(1<<j))){
for(int take = 0;take < n;take++){
if(dp[mask][i][take]>=1e18) continue;
int tmp = min((x[j]-x[i]+l)%l,(x[i]-x[j]+l)%l);
int tt = dp[mask][i][take]+tmp;
dp[mask^(1<<j)][j][take+(tt<=t[j])] = min(dp[mask^(1<<j)][j][take+(tt<=t[j])],tt);
}
}
}
}
}
}
int ans = 0;
for(int mask = 0;mask < (1<<n);mask++){
for(int i = 0;i < n;i++){
for(int j = 0;j <= n;j++){
if(dp[mask][i][j]<1e18){
ans = max(ans,j);
}
}
}
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
1344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
18 ms |
8404 KB |
Output is correct |
7 |
Correct |
1 ms |
816 KB |
Output is correct |
8 |
Correct |
3 ms |
2260 KB |
Output is correct |
9 |
Correct |
16 ms |
8532 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
20 ms |
8532 KB |
Output is correct |
13 |
Correct |
19 ms |
8528 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
11 ms |
8532 KB |
Output is correct |
17 |
Correct |
11 ms |
8408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
1344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
18 ms |
8404 KB |
Output is correct |
7 |
Correct |
1 ms |
816 KB |
Output is correct |
8 |
Correct |
3 ms |
2260 KB |
Output is correct |
9 |
Correct |
16 ms |
8532 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
20 ms |
8532 KB |
Output is correct |
13 |
Correct |
19 ms |
8528 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
11 ms |
8532 KB |
Output is correct |
17 |
Correct |
11 ms |
8408 KB |
Output is correct |
18 |
Correct |
100 ms |
33152 KB |
Output is correct |
19 |
Correct |
3 ms |
2260 KB |
Output is correct |
20 |
Correct |
16 ms |
8532 KB |
Output is correct |
21 |
Correct |
100 ms |
33132 KB |
Output is correct |
22 |
Correct |
2 ms |
1236 KB |
Output is correct |
23 |
Correct |
220 ms |
65968 KB |
Output is correct |
24 |
Correct |
34 ms |
16724 KB |
Output is correct |
25 |
Correct |
93 ms |
33056 KB |
Output is correct |
26 |
Correct |
89 ms |
33136 KB |
Output is correct |
27 |
Correct |
1 ms |
724 KB |
Output is correct |
28 |
Correct |
2 ms |
1236 KB |
Output is correct |
29 |
Correct |
273 ms |
65968 KB |
Output is correct |
30 |
Correct |
230 ms |
65968 KB |
Output is correct |
31 |
Correct |
49 ms |
33108 KB |
Output is correct |
32 |
Correct |
24 ms |
16724 KB |
Output is correct |
33 |
Correct |
134 ms |
65964 KB |
Output is correct |
34 |
Correct |
141 ms |
65868 KB |
Output is correct |
35 |
Correct |
152 ms |
65972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
1344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
18 ms |
8404 KB |
Output is correct |
7 |
Correct |
1 ms |
816 KB |
Output is correct |
8 |
Correct |
3 ms |
2260 KB |
Output is correct |
9 |
Correct |
16 ms |
8532 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
20 ms |
8532 KB |
Output is correct |
13 |
Correct |
19 ms |
8528 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
11 ms |
8532 KB |
Output is correct |
17 |
Correct |
11 ms |
8408 KB |
Output is correct |
18 |
Runtime error |
1101 ms |
266688 KB |
Execution killed with signal 11 |
19 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
2 ms |
1344 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
468 KB |
Output is correct |
6 |
Correct |
18 ms |
8404 KB |
Output is correct |
7 |
Correct |
1 ms |
816 KB |
Output is correct |
8 |
Correct |
3 ms |
2260 KB |
Output is correct |
9 |
Correct |
16 ms |
8532 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
20 ms |
8532 KB |
Output is correct |
13 |
Correct |
19 ms |
8528 KB |
Output is correct |
14 |
Correct |
1 ms |
468 KB |
Output is correct |
15 |
Correct |
1 ms |
724 KB |
Output is correct |
16 |
Correct |
11 ms |
8532 KB |
Output is correct |
17 |
Correct |
11 ms |
8408 KB |
Output is correct |
18 |
Correct |
100 ms |
33152 KB |
Output is correct |
19 |
Correct |
3 ms |
2260 KB |
Output is correct |
20 |
Correct |
16 ms |
8532 KB |
Output is correct |
21 |
Correct |
100 ms |
33132 KB |
Output is correct |
22 |
Correct |
2 ms |
1236 KB |
Output is correct |
23 |
Correct |
220 ms |
65968 KB |
Output is correct |
24 |
Correct |
34 ms |
16724 KB |
Output is correct |
25 |
Correct |
93 ms |
33056 KB |
Output is correct |
26 |
Correct |
89 ms |
33136 KB |
Output is correct |
27 |
Correct |
1 ms |
724 KB |
Output is correct |
28 |
Correct |
2 ms |
1236 KB |
Output is correct |
29 |
Correct |
273 ms |
65968 KB |
Output is correct |
30 |
Correct |
230 ms |
65968 KB |
Output is correct |
31 |
Correct |
49 ms |
33108 KB |
Output is correct |
32 |
Correct |
24 ms |
16724 KB |
Output is correct |
33 |
Correct |
134 ms |
65964 KB |
Output is correct |
34 |
Correct |
141 ms |
65868 KB |
Output is correct |
35 |
Correct |
152 ms |
65972 KB |
Output is correct |
36 |
Runtime error |
1101 ms |
266688 KB |
Execution killed with signal 11 |
37 |
Halted |
0 ms |
0 KB |
- |