Submission #580260

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580260	2022-06-20T21:07:59 Z	HeyYouNotYouYou	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	2000 ms	132416 KB

ho_t3

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 250,INF=1e12;
int n , L;
int x[N] , t[N];
map<pair<pair<int,int>,pair<int,int>>,int>dp;
int solve(int l ,int r , int time , int pos){
  if(l==r) return 0;
  if(dp.count({{l,r},{time,pos}})) return dp[{{l,r},{time,pos}}];
  if(pos){
    return dp[{{l,r},{time,pos}}]=max(
    solve(l,r+1,time+(x[r+1]-x[r]),1)+(time+(x[r+1]-x[r])<=t[r+1]),
    solve(l,r+1,time+(L-x[l])+x[r],0)+(time+(L-x[l])+x[r]<=t[l]));
  }
  else{
    return dp[{{l,r},{time,pos}}]=max(
    solve(l-1,r,time+(x[l]-x[l-1]),0)+(time+(x[l]-x[l-1])<=t[l-1]),
    solve(l-1,r,time+(L-x[l])+x[r],1)+(time+(L-x[l])+x[r]<=t[r]));
  }
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n >> L;
  //memset(dp,-1,sizeof dp);
  for(int i = 1 ; i <= n ; i ++) cin>>x[i];
  for(int i = 1 ; i <= n ; i ++) cin>>t[i];
  cout<<max(solve(n,1,L-x[n],0)+(L-x[n]<=t[n]),solve(n,1,x[1],1)+(x[1]<=t[1]));
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	6 ms	1492 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Correct	2 ms	596 KB	Output is correct
21	Correct	6 ms	1492 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	12 ms	2772 KB	Output is correct
24	Correct	3 ms	852 KB	Output is correct
25	Correct	7 ms	1492 KB	Output is correct
26	Correct	7 ms	1492 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	304 KB	Output is correct
29	Correct	15 ms	2792 KB	Output is correct
30	Correct	14 ms	2772 KB	Output is correct
31	Correct	6 ms	1492 KB	Output is correct
32	Correct	4 ms	852 KB	Output is correct
33	Correct	2 ms	596 KB	Output is correct
34	Correct	2 ms	468 KB	Output is correct
35	Correct	2 ms	524 KB	Output is correct

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Execution timed out	2101 ms	132416 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-

Subtask #4

0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	304 KB	Output is correct
3	Correct	1 ms	340 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	2 ms	468 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	2 ms	468 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	468 KB	Output is correct
13	Correct	2 ms	468 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	1 ms	212 KB	Output is correct
16	Correct	2 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	6 ms	1492 KB	Output is correct
19	Correct	1 ms	300 KB	Output is correct
20	Correct	2 ms	596 KB	Output is correct
21	Correct	6 ms	1492 KB	Output is correct
22	Correct	1 ms	340 KB	Output is correct
23	Correct	12 ms	2772 KB	Output is correct
24	Correct	3 ms	852 KB	Output is correct
25	Correct	7 ms	1492 KB	Output is correct
26	Correct	7 ms	1492 KB	Output is correct
27	Correct	1 ms	212 KB	Output is correct
28	Correct	1 ms	304 KB	Output is correct
29	Correct	15 ms	2792 KB	Output is correct
30	Correct	14 ms	2772 KB	Output is correct
31	Correct	6 ms	1492 KB	Output is correct
32	Correct	4 ms	852 KB	Output is correct
33	Correct	2 ms	596 KB	Output is correct
34	Correct	2 ms	468 KB	Output is correct
35	Correct	2 ms	524 KB	Output is correct
36	Execution timed out	2101 ms	132416 KB	Time limit exceeded
37	Halted	0 ms	0 KB	-