#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 200 + 3;
const ll inf = 1e9 + 7;
typedef pair<int,int> LL;
ll n,lens,a[N],dp[N][N][N][2],lim[N];
ll ans;
struct Node{
ll val,L,R,p,lr;
};
bool operator < (Node a,Node b){
return a.val > b.val;
}
priority_queue<Node> pq;
ll Ask(ll L,ll R){
return lens - a[L] + a[R];
}
void Minimize(ll L,ll R,ll p,ll lr,ll val){
if (dp[L][R][p][lr] <= val) return; ans = max(ans,p);
dp[L][R][p][lr] = val; pq.push({val,L,R,p,lr});
}
void process(ll L,ll R,ll p,ll lr){}
int main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n>>lens;
for (ll i = 1;i <= n;i++) cin>>a[i];
for (ll i = 1;i <= n;i++) cin>>lim[i];
for (ll i = 0;i <= n;i++)
for (ll j = 0;j <= n;j++)
for (ll l = 0;l <= n;l++) dp[i][j][l][0] = dp[i][j][l][1] = inf;
dp[0][0][0][0] = dp[0][0][0][1] = 0;
pq.push({0,0,0,0,0}); pq.push({0,0,0,0,1});
while(!pq.empty()){
Node t = pq.top(); pq.pop();
ll L = t.L,R = t.R,p = t.p,lr = t.lr,A = t.val,now1,now2;
if (L - R == 1) continue;
ll nxtL = L - 1,nxtR = R + 1;
if (!L) nxtL = n;
if (!lr){
now1 = A + a[L] - a[nxtL],now2 = A + Ask(L,R + 1);
if (L == 0) now1 = A + lens - a[nxtL];
//cout<<now1; return 0;
}
else{
now1 = A + Ask(nxtL,R),now2 = A + a[R + 1] - a[R];
}
//cout<<now1<<" "<<lim[nxtL]; return 0;
if (now1 <= lim[nxtL]) Minimize(nxtL,R,p + 1,0,now1);
else Minimize(nxtL,R,p,0,now1);
if (now2 <= lim[R + 1]) Minimize(L,R + 1,p + 1,1,now2);
else Minimize(L,R + 1,p,1,now2);
}
cout<<ans;
}
Compilation message
ho_t3.cpp: In function 'void Minimize(int, int, int, int, int)':
ho_t3.cpp:26:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
26 | if (dp[L][R][p][lr] <= val) return; ans = max(ans,p);
| ^~
ho_t3.cpp:26:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
26 | if (dp[L][R][p][lr] <= val) return; ans = max(ans,p);
| ^~~
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:52:25: warning: unused variable 'nxtR' [-Wunused-variable]
52 | ll nxtL = L - 1,nxtR = R + 1;
| ^~~~
ho_t3.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
37 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
620 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
620 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
620 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
512 KB |
Output is correct |
| 6 |
Correct |
1 ms |
620 KB |
Output is correct |
| 7 |
Correct |
1 ms |
492 KB |
Output is correct |
| 8 |
Correct |
1 ms |
492 KB |
Output is correct |
| 9 |
Correct |
1 ms |
620 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
748 KB |
Output is correct |
| 13 |
Correct |
1 ms |
620 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Incorrect |
1 ms |
620 KB |
Output isn't correct |
| 17 |
Halted |
0 ms |
0 KB |
- |
