#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define FF first.first
#define FS first.second
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e13, P=998244353;
int n, ANS;
ll L;
ll dp[205][205][205][2];
void solve(){
cin>>n>>L;
vector<ll> a(n), T(n);
for (auto &x:a)cin>>x;
for (auto &x:T)cin>>x;
for (int i=0; i<=n; i++)
for (int j=0; j<=n; j++)
for (int k=0; k<=n; k++)
dp[i][j][k][0]=dp[i][j][k][1]=INF;
dp[n][0][0][0]=dp[n][0][0][1]=0;
for (int l=n; l>=0; l--){
for (int r=0; r<=l; r++){
// cout<<r<<" "<<l<<" "<<r+(n-l)<<endl;
for (int ans=0; ans<=n; ans++){
for (int i=0; i<2; i++){
ll curl=(l==n?L:a[l]);
ll curr=(r==0?0:a[r-1]);
ll t=dp[l][r][ans][i], len=curr+(L-curl);
if(t>=INF)continue;
if(l>0){
ll tt=t+(curl-a[l-1])+((ll)(i^0)*len);
int Ans=ans+(tt<=T[l-1]);
ll &next=dp[l-1][r][Ans][0];
next=min(tt, next);
ANS=max(Ans, ANS);
}
if(r<n){
ll tt=t+(a[r]-curr)+((ll)(i^1)*len);
int Ans=ans+(tt<=T[r+0]);
ll &next=dp[l][r+1][Ans][1];
next=min(tt, next);
ANS=max(Ans, ANS);
}
}
}
}
}
cout<<ANS;
}
main(){ios_base::sync_with_stdio(false), cin.tie(0);
int T=1;
//cin>>T;
while(T--){
solve();
}
}
Compilation message
ho_t3.cpp:61:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
61 | main(){ios_base::sync_with_stdio(false), cin.tie(0);
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
588 KB |
Output is correct |
4 |
Correct |
0 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
792 KB |
Output is correct |
7 |
Correct |
0 ms |
460 KB |
Output is correct |
8 |
Correct |
0 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
844 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
844 KB |
Output is correct |
13 |
Correct |
1 ms |
844 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
0 ms |
588 KB |
Output is correct |
16 |
Incorrect |
0 ms |
844 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
588 KB |
Output is correct |
4 |
Correct |
0 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
792 KB |
Output is correct |
7 |
Correct |
0 ms |
460 KB |
Output is correct |
8 |
Correct |
0 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
844 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
844 KB |
Output is correct |
13 |
Correct |
1 ms |
844 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
0 ms |
588 KB |
Output is correct |
16 |
Incorrect |
0 ms |
844 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
588 KB |
Output is correct |
4 |
Correct |
0 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
792 KB |
Output is correct |
7 |
Correct |
0 ms |
460 KB |
Output is correct |
8 |
Correct |
0 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
844 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
844 KB |
Output is correct |
13 |
Correct |
1 ms |
844 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
0 ms |
588 KB |
Output is correct |
16 |
Incorrect |
0 ms |
844 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
588 KB |
Output is correct |
4 |
Correct |
0 ms |
460 KB |
Output is correct |
5 |
Correct |
0 ms |
460 KB |
Output is correct |
6 |
Correct |
1 ms |
792 KB |
Output is correct |
7 |
Correct |
0 ms |
460 KB |
Output is correct |
8 |
Correct |
0 ms |
716 KB |
Output is correct |
9 |
Correct |
1 ms |
844 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
844 KB |
Output is correct |
13 |
Correct |
1 ms |
844 KB |
Output is correct |
14 |
Correct |
0 ms |
460 KB |
Output is correct |
15 |
Correct |
0 ms |
588 KB |
Output is correct |
16 |
Incorrect |
0 ms |
844 KB |
Output isn't correct |
17 |
Halted |
0 ms |
0 KB |
- |