#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,l;
cin>>n>>l;
vector<int> tr(n);
vector<int> tl(n);
vector<int> rd(n+1);
vector<int> ld(n+1);
vector<pair<int,int>> cl(n);
vector<pair<int,int>> cr(n);
rd[0] = 0;
ld[0] = 0;
for(int i = 0;i<n;i++)
{
//cin>>rd[i+1];
//ld[n-i] = l-rd[i+1];
cin>>cr[i].first;
cr[i].first%=l;
cl[n-i-1].first = l-cr[i].first;
}
for(int i = 0;i<n;i++)
{
//cin>>tr[i];
//tl[n-i-1] = tr[i];
cin>>cr[i].second;
cl[n-i-1].second = cr[i].second;
}
sort(cl.begin(),cl.end());
sort(cr.begin(),cr.end());
for(int i = 0;i<n;i++)
{
rd[i+1] = cr[i].first;
ld[i+1] = cl[i].first;
tr[i] = cr[i].second;
tl[i] = cl[i].second;
}
long long m = 1000000000;
m *=m;
long long dp[n+1][n+1][n+1][2];
dp[0][0][0][0] = 0;
dp[0][0][0][1] = 0;
for(int i = 1;i<n+1;i++)
{
dp[0][0][i][0] = m;
dp[0][0][i][1] = m;
}
for(int i = 1;i<n+1;i++)
{
for(int q = 0;q<n+1;q++)
{
dp[i][0][q][0] = m;
dp[i][0][q][1] = m;
dp[i][0][q][0] = dp[i-1][0][q][0]-ld[i-1]+ld[i];
if(q!=0 && dp[i-1][0][q-1][0]+ld[i]-ld[i-1] <= tl[i-1])
{
//if(q==1&&i==1) cout<<"d"<<ld[i]<<" "<<ld[i-1]<<"\n";
dp[i][0][q][0] = min(dp[i][0][q][0],dp[i-1][0][q-1][0]+ld[i]-ld[i-1]);
}
dp[i][0][q][1] = 2*dp[i][0][q][0];
}
}
for(int j = 1;j<n+1;j++)
{
for(int q = 0;q<n+1;q++)
{
dp[0][j][q][1] = m;
dp[0][j][q][0] = m;
dp[0][j][q][1] = dp[0][j-1][q][1]-rd[j-1]+rd[j];
if(q!= 0 &&dp[0][j-1][q-1][1]+rd[j]-rd[j-1] <= tr[j-1])
{
dp[0][j][q][1] = min(dp[0][j][q][1],dp[0][j-1][q-1][1]+rd[j]-rd[j-1]);
}
dp[0][j][q][0] = 2*dp[0][j][q][1];
}
}
for(int i = 1;i<n+1;i++)
{
for(int j = 1;j<n+1;j++)
{
for(int q = 0;q<n+1;q++)
{
dp[i][j][q][0] = m;
dp[i][j][q][1] = m;
if(i!= 0)
{
dp[i][j][q][0] = min(dp[i-1][j][q][0]-ld[i-1]+ld[i],dp[i-1][j][q][1]+rd[j]+ld[i]);
}
if(q!=0 && dp[i-1][j][q-1][0]+ld[i]-ld[i-1] <= tl[i-1])
{
dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][0]+ld[i]-ld[i-1]);
}
if(q!=0 && dp[i-1][j][q-1][1]+rd[j]+ld[i] <=tl[i-1])
{
dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][0]+ld[i]+rd[j]);
}
//if((i == 1 && j == 1)&&(q == 1))
//{cout<<"a"<<"\n";}
if(j != 0)
{
/*if((i == 1 && j == 1)&&(q == 1))
{
cout<<dp[i][j][q][1]<<"\n";
}*/
dp[i][j][q][1] = min(dp[i][j-1][q][0]+ld[i]+rd[j],dp[i][j-1][q][1]-rd[j-1]+rd[j]);
/*if((i == 1 && j == 1)&&(q == 1))
{
cout<<dp[i][j][q][1]<<"\n";
}*/
}
if(q!= 0 && dp[i][j-1][q-1][0] + ld[i]+rd[j] <= tr[j-1])
{
//if((i == 1 && j == 1)&&(q == 1)) cout<<"b"<<"\n";
dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][0] + ld[i]+rd[j]);
}
if(q != 0 && dp[i][j-1][q-1][1] + rd[j]-rd[j-1] <= tr[j-1])
{
//if((i == 1 && j == 1)&&(q == 1)) cout<<"a"<<"\n";
dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][0]-rd[j-1]+rd[j]);
}
}
}
}
/*for(int i = 0;i<n+1;i++)
{
for(int j = 0;j<n+1;j++)
{
for(int q = 0;q<n+1;q++)
{
for(int w = 0;w<2;w++)
{
cout<<dp[i][j][q][w]<<" dp["<<i<<"]["<<j<<"]["<<q<<"]["<<w<<"]\n";;
}
}
}
}*/
int ans = 0;
for(int i = 0;i<n+1;i++)
{
for(int j = 0;j<n+1;j++)
{
for(int q = 0;q<n+1;q++)
{
if(dp[i][j][q][0] <m) ans = max(ans,q);
if(dp[i][j][q][1] < m) ans = max(ans,q);
}
}
}
cout<<ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
564 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
564 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
564 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
1 ms |
564 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
