#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
using namespace std;
#define LOCALIO "C:/Users/admin/Documents/Code/"
const ll INF=1000000000000000000;
ll n, L, a[205], t[205], res;
ll dp[205][205][205][2];
bool check[205][205][205][2];
ll dis(ll l, ll r, ll di)
{
if (!di)
{
if (r<l)
return a[r]-a[l]+L;
return a[r]-a[l];
}
if (r>l)
return a[l]-a[r]+L;
return a[l]-a[r];
}
ll calc(ll l, ll r, ll k, ll di)
{
if (k<0) return INF;
if (check[l][r][k][di])
return dp[l][r][k][di];
if (l==r)
return dp[l][r][k][di];
ll ans=INF;
if (!di)
{
ll A=calc((l+1)%n, r, k-1, 0);
ll B=calc((l+1)%n, r, k, 0);
ll C=calc((l+1)%n, r, k-1, 1);
ll D=calc((l+1)%n, r, k, 1);
ll dis1=dis((l+1)%n, l, 1), dis2=dis(r, l, 1);
if (t[l]>=A+dis1)
ans=min(ans, A+dis1);
if (t[l]<B+dis1)
ans=min(ans, B+dis1);
if (t[l]>=C+dis2)
ans=min(ans, C+dis2);
if (t[l]<D+dis2)
ans=min(ans, D+dis2);
}
else
{
ll A=calc(l, (r-1+n)%n, k-1, 0);
ll B=calc(l, (r-1+n)%n, k, 0);
ll C=calc(l, (r-1+n)%n, k-1, 1);
ll D=calc(l, (r-1+n)%n, k, 1);
ll dis1=dis((r-1+n)%n, r, 0), dis2=dis(l, r, 0);
if (t[r]>=A+dis2)
ans=min(ans, A+dis2);
if (t[r]<B+dis2)
ans=min(ans, B+dis2);
if (t[r]>=C+dis1)
ans=min(ans, C+dis1);
if (t[r]<D+dis1)
ans=min(ans, D+dis1);
}
dp[l][r][k][di]=ans;
check[l][r][k][di]=1;
// if (ans!=INF)
// cout << l << " " << r << " " << k << " " << di << " " << ans << "\n";
if (l==(r+1)%n && ans!=INF)
res=max(res, k);
return ans;
}
int main()
{
#ifdef LOCAL
freopen( LOCALIO "input.txt","r",stdin) ;
freopen( LOCALIO "output.txt","w",stdout) ;
#endif
ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
// freopen("FIBONACCI.inp","r",stdin);
// freopen("FIBONACCI.out","w",stdout);
cin >> n >> L;
for (ll i=0; i<n; i++)
cin >> a[i];
for (ll i=0; i<n; i++)
cin >> t[i];
for (ll i=0; i<n; i++)
for (ll j=0; j<n; j++)
for (ll k=0; k<=n; k++)
for (ll di=0; di<2; di++)
dp[i][j][k][di]=INF;
dp[0][0][t[0]>=a[0]][0]=a[0];
dp[n-1][n-1][t[n-1]>=L-a[n-1]][0]=L-a[n-1];
for (ll i=0; i<n; i++)
for (ll j=0; j<n; j++)
for (ll k=0; k<=n; k++)
for (ll z=0; z<2; z++)
calc(i, j, k, z);
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
580 KB |
Output is correct |
| 4 |
Correct |
1 ms |
456 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
580 KB |
Output is correct |
| 4 |
Correct |
1 ms |
456 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
580 KB |
Output is correct |
| 4 |
Correct |
1 ms |
456 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
580 KB |
Output is correct |
| 4 |
Correct |
1 ms |
456 KB |
Output is correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Correct |
1 ms |
844 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
724 KB |
Output is correct |
| 9 |
Correct |
1 ms |
852 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Incorrect |
1 ms |
324 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
