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;
const int MAXN = 205;
const int INF = 2e9 + 5;
int n, l, ans;
int X[MAXN], t[MAXN];
int dp[MAXN][MAXN][MAXN][2];
int f(int x)
{
return min(x, l - x);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> l;
for(int i = 1; i <= n; i++)
{
cin >> X[i];
}
for(int i = 1; i <= n; i++)
{
cin >> t[i];
}
for(int i = 0; i <= n; i++)
{
for(int j = 0; j <= n; j++)
{
for(int k = 0; k <= n; k++)
{
for(int h = 0; h < 2; h++)
{
dp[i][j][k][h] = INF;
}
}
}
}
dp[0][0][0][0] = 0;
priority_queue <tuple <int, int, int, int, int> > pq;
pq.push(make_tuple(0, 0, 0, 0, 0));
while(pq.empty() == false)
{
int d, l, r, k, h;
tie(d, l, r, k, h) = pq.top();
pq.pop();
d = -d;
ans = max(ans, k);
if(d == dp[l][r][k][h])
{
int prv = l - 1;
if(prv == -1)
{
prv = n;
}
if(prv != r)
{
int dist = d + f(abs(X[prv] - (h ? X[r] : X[l])));
if(dist <= t[prv] and prv != 0)
{
if(dp[prv][r][k + 1][0] > dist)
{
dp[prv][r][k + 1][0] = dist;
pq.push(make_tuple(-dist, prv, r, k + 1, 0));
}
}
else
{
if(dp[prv][r][k][0] > dist)
{
dp[prv][r][k][0] = dist;
pq.push(make_tuple(-dist, prv, r, k, 0));
}
}
}
int nxt = r + 1;
if(nxt != l)
{
int dist = d + f(abs(X[nxt] - (h ? X[r] : X[l])));
if(dist <= t[nxt] and nxt != 0)
{
if(dp[l][nxt][k + 1][1] > dist)
{
dp[l][nxt][k + 1][1] = dist;
pq.push(make_tuple(-dist, l, nxt, k + 1, 1));
}
}
else
{
if(dp[l][nxt][k][1] > dist)
{
dp[l][nxt][k][1] = dist;
pq.push(make_tuple(-dist, l, nxt, k, 1));
}
}
}
}
}
cout << ans << '\n';
}
# | 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... |