This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll dp[205][205][2][205];
const ll INF = 1e15;
ll a[205];
ll b[205];
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
ll n, l;
cin >> n >> l;
for(int i=1; i<=n; i++){
cin >> a[i];
}
for(int i=1; i<=n; i++){
cin >> b[i];
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(int k=0; k<=1; k++){
for(int r=0; r<=n; r++){
dp[i][j][k][r] = INF;
}
}
}
}
dp[1][1][1][(b[1] >= a[1])] = a[1];
dp[n][n][0][(b[n] >= l-a[n])] = l-a[n];
for(int len=1; len<n; len++){
for(int i=n; i>=1; i--){
int ost = len-(n-i+1);
if(ost <= 0) break;
int j = ost;
for(int k=0; k<=n; k++){
ll vreme = dp[i][j][0][k];
int novi = (vreme+a[i]-a[i-1] <= b[i-1]) + k;
dp[i-1][j][0][novi] = min(dp[i-1][j][0][novi], vreme+a[i]-a[i-1]);
novi = (vreme+l-a[i]+a[j+1] <= b[j+1]) + k;
dp[i][j+1][1][novi] = min(dp[i][j+1][1][novi], vreme+l-a[i]+a[j+1]);
vreme = dp[i][j][1][k];
novi = (vreme+a[j+1]-a[j] <= b[j+1]) + k;
dp[i][j+1][1][novi] = min(dp[i][j+1][1][novi], vreme+a[j+1]-a[j]);
novi = (vreme+l-a[i-1]+a[j] <= b[i-1]) + k;
dp[i-1][j][0][novi] = min(dp[i-1][j][0][novi], vreme+l-a[i-1]+a[j]);
}
}
for(int k=0; k<=n; k++){
ll vreme = dp[1][len][1][k];
int novi = (vreme+a[len+1]-a[len] <= b[len+1]) + k;
dp[1][len+1][1][novi] = min(dp[1][len+1][1][novi], vreme+a[len+1]-a[len]);
novi = (vreme+l-a[n]+a[len] <= b[n]) + k;
dp[n][len][0][novi] = min(dp[n][len][0][novi], vreme+l-a[n]+a[len]);
int j = n-len+1;
vreme = dp[j][n][0][k];
novi = (vreme+a[j]-a[j-1] <= b[j-1]) + k;
dp[j-1][n][0][novi] = min(dp[j-1][n][0][novi], vreme+a[j]-a[j-1]);
novi = (vreme+a[1]+l-a[j] <= b[1]) + k;
dp[j][1][1][novi] = min(dp[j][1][1][novi], vreme+a[1]+l-a[j]);
}
}
int res = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
for(int k=0; k<=1; k++){
for(int r=0; r<=n; r++){
if(dp[i][j][k][r] != INF) res = max(res, r);
}
}
}
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |