#include<bits/stdc++.h>
using namespace std;
const int nmax=2e2+5;
int n,circle;
int where[nmax],t_max[nmax];
int dp[nmax][nmax][nmax][2];//min time to get to state left position, right position, satisfied stamps, on left/right
priority_queue< pair< pair< pair< pair<int/*time*/,int/*left position*/>,int/*right position*/>,int/*satisfied*/>,int/*on left/right*/> > pq;
int calc_dist(int a,int b)
{
int ret=abs(a-b);
return min(ret,circle-ret);
}
void make_state(int t,int l_now,int r_now,int ok,bool side)
{
pq.push({{{{-t,l_now},r_now},ok},side});
}
int main()
{
scanf("%i%i",&n,&circle);
for(int i=1;i<=n;i++)scanf("%i",&where[i]);
for(int i=1;i<=n;i++)scanf("%i",&t_max[i]);
int MX_valid=0;
for(int i=1;i<=n;i++)MX_valid=max(MX_valid,t_max[i]);
//go to 1
make_state(calc_dist(0,where[1]),1,n+1,calc_dist(0,where[1])<=t_max[1],0);
//go to n
make_state(calc_dist(0,where[n]),0,n,calc_dist(0,where[n])<=t_max[n],1);
int output=0;
while(pq.size())
{
pair< pair< pair< pair<int/*time*/,int/*left position*/>,int/*right position*/>,int/*satisfied*/>,int/*on left/right*/> use=pq.top();
pq.pop();
int t_now=-use.first.first.first.first;
int l_now=use.first.first.first.second;
int r_now=use.first.first.second;
int satisfied=use.first.second;
bool side=use.second;
int location=(side==0?l_now:r_now);
output=max(output,satisfied);
if(dp[l_now][r_now][satisfied][side])continue;
dp[l_now][r_now][satisfied][side]=t_now;
//[l_now+1...r_now-1] are remaining
if(l_now==r_now)continue;
if(t_now>MX_valid)continue;
//go to l_now
make_state(t_now+calc_dist(location,where[l_now+1]),l_now+1,r_now,satisfied+(t_now+calc_dist(location,where[l_now+1])<=t_max[l_now+1]),0);
//go to r_now
make_state(t_now+calc_dist(location,where[r_now-1]),l_now,r_now-1,satisfied+(t_now+calc_dist(location,where[r_now-1])<=t_max[r_now-1]),1);
}
printf("%i\n",output);
return 0;
}
Compilation message
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i%i",&n,&circle);
~~~~~^~~~~~~~~~~~~~~~~~~
ho_t3.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%i",&where[i]);
~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:25:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=n;i++)scanf("%i",&t_max[i]);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
