#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);
| ^~~~
| # |
Verdict |
Execution time |
Memory |
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 |
844 KB |
Output is correct |
| 7 |
Correct |
0 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
716 KB |
Output is correct |
| 9 |
Correct |
1 ms |
844 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
844 KB |
Output is correct |
| 13 |
Correct |
0 ms |
844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
0 ms |
588 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
844 KB |
Output is correct |
| 7 |
Correct |
0 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
716 KB |
Output is correct |
| 9 |
Correct |
1 ms |
844 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
844 KB |
Output is correct |
| 13 |
Correct |
0 ms |
844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
0 ms |
588 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
844 KB |
Output is correct |
| 7 |
Correct |
0 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
716 KB |
Output is correct |
| 9 |
Correct |
1 ms |
844 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
844 KB |
Output is correct |
| 13 |
Correct |
0 ms |
844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
0 ms |
588 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
844 KB |
Output is correct |
| 7 |
Correct |
0 ms |
460 KB |
Output is correct |
| 8 |
Correct |
1 ms |
716 KB |
Output is correct |
| 9 |
Correct |
1 ms |
844 KB |
Output is correct |
| 10 |
Correct |
0 ms |
332 KB |
Output is correct |
| 11 |
Correct |
0 ms |
204 KB |
Output is correct |
| 12 |
Correct |
1 ms |
844 KB |
Output is correct |
| 13 |
Correct |
0 ms |
844 KB |
Output is correct |
| 14 |
Correct |
1 ms |
460 KB |
Output is correct |
| 15 |
Correct |
0 ms |
588 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
844 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
