답안 #888072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888072	2023-12-15T22:14:28 Z	amirhoseinfar1385	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	54 ms	145748 KB

ho_t3

#include<bits/stdc++.h>
using namespace std;
const long long maxn=210,inf=1000000000000000;
pair<long long,long long>dp[maxn][maxn][maxn];
long long n,allx[maxn],allt[maxn],L;
long long res=0;
long long fas(long long a,long long b){
	 if (b <= a)
        return (a - b);
    return L - (b- a);
}

void upddp(long long l,long long r){
	//cout<<l<<" "<<r<<" "<<dp[l][r][0].first<<" "<<dp[l][r][0].second<<"\n";
	long long ll=(l-1)+n,rr=r+1;
	ll%=n;
	rr%=n;
	for(long long i=0;i<n;i++){
		if(dp[l][r][i].first!=inf){
			//cout<<l<<" "<<r<<" "<<i<<" "<<dp[l][r][i].first<<" "<<dp[l][r][i].second<<'\n';
			dp[ll][r][i].first=min(dp[ll][r][i].first,dp[l][r][i].first+fas(allx[l],allx[ll]));
			dp[ll][r][i].second=min(dp[ll][r][i].second,dp[ll][r][i].first+fas(allx[r],allx[ll]));
			if(fas(allx[l],allx[ll])+dp[l][r][i].first<=allt[ll]){
				dp[ll][r][i+1].first=min(dp[ll][r][i+1].first,dp[l][r][i].first+fas(allx[l],allx[ll]));
				dp[ll][r][i+1].second=min(dp[ll][r][i+1].second,dp[ll][r][i+1].first+fas(allx[r],allx[ll]));
				res=max(res,i+1);
			}
			dp[l][rr][i].second=min(dp[l][rr][i].second,dp[l][r][i].second+fas(allx[rr],allx[r]));
			dp[l][rr][i].first=min(dp[l][rr][i].first,dp[l][rr][i].second+fas(allx[rr],allx[l]));
			if(fas(allx[rr],allx[r])+dp[l][r][i].second<=allt[rr]){
				dp[l][rr][i+1].second=min(dp[l][rr][i+1].second,dp[l][r][i].second+fas(allx[rr],allx[r]));
				dp[l][rr][i+1].first=min(dp[l][rr][i+1].first,dp[l][rr][i+1].second+fas(allx[rr],allx[l]));
				res=max(res,i+1);
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(long long i=0;i<maxn;i++){
		for(long long j=0;j<maxn;j++){
			for(long long h=0;h<maxn;h++){
				dp[i][j][h]=make_pair(inf,inf);
			}
		}
	}
	cin>>n>>L;
	for(long long i=0;i<n;i++){
		cin>>allx[i];
	}
	for(long long i=0;i<n;i++){
		cin>>allt[i];
	}
	if(n==1){
		if(min(allx[0],fas(0,allx[0]))<=allt[0]){
			cout<<1<<endl;
			return 0;
		}
		cout<<0<<endl;
		return 0;
	}
	if(allx[0]<=allt[0]){
		dp[0][0][0]=dp[0][0][1]=make_pair(allx[0],allx[0]);
		res=1;
	}
	else{
		dp[0][0][0]=make_pair(allx[0],allx[0]);
	}
	if(fas(0,allx[n-1])<=allt[n-1]){
		dp[n-1][n-1][0]=dp[n-1][n-1][1]=make_pair(fas(0,allx[n-1]),fas(0,allx[n-1]));
		res=1;
	}
	else{
		dp[n-1][n-1][0]=make_pair(fas(0,allx[n-1]),fas(0,allx[n-1]));
	}
	for(long long i=0;i<n-1;i++){
		for(long long l=n-1;l>=0;l--){
			upddp(l,(l+i)%n);
		}
	}
	cout<<res<<"\n";
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	145236 KB	Output is correct
2	Correct	20 ms	145232 KB	Output is correct
3	Correct	20 ms	145240 KB	Output is correct
4	Correct	21 ms	145380 KB	Output is correct
5	Correct	21 ms	145240 KB	Output is correct
6	Correct	20 ms	145236 KB	Output is correct
7	Correct	21 ms	145268 KB	Output is correct
8	Correct	20 ms	145244 KB	Output is correct
9	Correct	21 ms	145164 KB	Output is correct
10	Correct	20 ms	145240 KB	Output is correct
11	Correct	20 ms	145244 KB	Output is correct
12	Correct	22 ms	145244 KB	Output is correct
13	Correct	21 ms	145244 KB	Output is correct
14	Correct	20 ms	145244 KB	Output is correct
15	Correct	21 ms	145300 KB	Output is correct
16	Correct	20 ms	145244 KB	Output is correct
17	Correct	20 ms	145204 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	145236 KB	Output is correct
2	Correct	20 ms	145232 KB	Output is correct
3	Correct	20 ms	145240 KB	Output is correct
4	Correct	21 ms	145380 KB	Output is correct
5	Correct	21 ms	145240 KB	Output is correct
6	Correct	20 ms	145236 KB	Output is correct
7	Correct	21 ms	145268 KB	Output is correct
8	Correct	20 ms	145244 KB	Output is correct
9	Correct	21 ms	145164 KB	Output is correct
10	Correct	20 ms	145240 KB	Output is correct
11	Correct	20 ms	145244 KB	Output is correct
12	Correct	22 ms	145244 KB	Output is correct
13	Correct	21 ms	145244 KB	Output is correct
14	Correct	20 ms	145244 KB	Output is correct
15	Correct	21 ms	145300 KB	Output is correct
16	Correct	20 ms	145244 KB	Output is correct
17	Correct	20 ms	145204 KB	Output is correct
18	Correct	20 ms	145232 KB	Output is correct
19	Correct	21 ms	145332 KB	Output is correct
20	Correct	20 ms	145236 KB	Output is correct
21	Correct	20 ms	145236 KB	Output is correct
22	Correct	21 ms	145232 KB	Output is correct
23	Correct	20 ms	145244 KB	Output is correct
24	Correct	20 ms	145236 KB	Output is correct
25	Correct	20 ms	145412 KB	Output is correct
26	Correct	21 ms	145432 KB	Output is correct
27	Correct	21 ms	145236 KB	Output is correct
28	Correct	20 ms	145192 KB	Output is correct
29	Correct	20 ms	145244 KB	Output is correct
30	Correct	23 ms	145304 KB	Output is correct
31	Correct	20 ms	145280 KB	Output is correct
32	Correct	20 ms	145244 KB	Output is correct
33	Correct	21 ms	145288 KB	Output is correct
34	Correct	20 ms	145304 KB	Output is correct
35	Correct	21 ms	145360 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	145236 KB	Output is correct
2	Correct	20 ms	145232 KB	Output is correct
3	Correct	20 ms	145240 KB	Output is correct
4	Correct	21 ms	145380 KB	Output is correct
5	Correct	21 ms	145240 KB	Output is correct
6	Correct	20 ms	145236 KB	Output is correct
7	Correct	21 ms	145268 KB	Output is correct
8	Correct	20 ms	145244 KB	Output is correct
9	Correct	21 ms	145164 KB	Output is correct
10	Correct	20 ms	145240 KB	Output is correct
11	Correct	20 ms	145244 KB	Output is correct
12	Correct	22 ms	145244 KB	Output is correct
13	Correct	21 ms	145244 KB	Output is correct
14	Correct	20 ms	145244 KB	Output is correct
15	Correct	21 ms	145300 KB	Output is correct
16	Correct	20 ms	145244 KB	Output is correct
17	Correct	20 ms	145204 KB	Output is correct
18	Correct	41 ms	145232 KB	Output is correct
19	Correct	32 ms	145236 KB	Output is correct
20	Correct	25 ms	145244 KB	Output is correct
21	Correct	31 ms	145240 KB	Output is correct
22	Correct	35 ms	145236 KB	Output is correct
23	Correct	25 ms	145240 KB	Output is correct
24	Correct	23 ms	145416 KB	Output is correct
25	Correct	25 ms	145296 KB	Output is correct
26	Correct	22 ms	145244 KB	Output is correct
27	Correct	25 ms	145304 KB	Output is correct
28	Correct	23 ms	145316 KB	Output is correct
29	Correct	25 ms	145236 KB	Output is correct
30	Correct	26 ms	145364 KB	Output is correct
31	Correct	26 ms	145428 KB	Output is correct
32	Correct	23 ms	145232 KB	Output is correct
33	Correct	24 ms	145244 KB	Output is correct
34	Correct	22 ms	145292 KB	Output is correct
35	Correct	23 ms	145244 KB	Output is correct
36	Correct	22 ms	145348 KB	Output is correct
37	Correct	24 ms	145244 KB	Output is correct
38	Correct	22 ms	145244 KB	Output is correct
39	Correct	25 ms	145444 KB	Output is correct
40	Correct	23 ms	145444 KB	Output is correct
41	Correct	49 ms	145236 KB	Output is correct
42	Correct	32 ms	145236 KB	Output is correct
43	Correct	48 ms	145420 KB	Output is correct
44	Correct	33 ms	145232 KB	Output is correct
45	Correct	49 ms	145416 KB	Output is correct
46	Correct	35 ms	145488 KB	Output is correct

Subtask #4
75.0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	145236 KB	Output is correct
2	Correct	20 ms	145232 KB	Output is correct
3	Correct	20 ms	145240 KB	Output is correct
4	Correct	21 ms	145380 KB	Output is correct
5	Correct	21 ms	145240 KB	Output is correct
6	Correct	20 ms	145236 KB	Output is correct
7	Correct	21 ms	145268 KB	Output is correct
8	Correct	20 ms	145244 KB	Output is correct
9	Correct	21 ms	145164 KB	Output is correct
10	Correct	20 ms	145240 KB	Output is correct
11	Correct	20 ms	145244 KB	Output is correct
12	Correct	22 ms	145244 KB	Output is correct
13	Correct	21 ms	145244 KB	Output is correct
14	Correct	20 ms	145244 KB	Output is correct
15	Correct	21 ms	145300 KB	Output is correct
16	Correct	20 ms	145244 KB	Output is correct
17	Correct	20 ms	145204 KB	Output is correct
18	Correct	20 ms	145232 KB	Output is correct
19	Correct	21 ms	145332 KB	Output is correct
20	Correct	20 ms	145236 KB	Output is correct
21	Correct	20 ms	145236 KB	Output is correct
22	Correct	21 ms	145232 KB	Output is correct
23	Correct	20 ms	145244 KB	Output is correct
24	Correct	20 ms	145236 KB	Output is correct
25	Correct	20 ms	145412 KB	Output is correct
26	Correct	21 ms	145432 KB	Output is correct
27	Correct	21 ms	145236 KB	Output is correct
28	Correct	20 ms	145192 KB	Output is correct
29	Correct	20 ms	145244 KB	Output is correct
30	Correct	23 ms	145304 KB	Output is correct
31	Correct	20 ms	145280 KB	Output is correct
32	Correct	20 ms	145244 KB	Output is correct
33	Correct	21 ms	145288 KB	Output is correct
34	Correct	20 ms	145304 KB	Output is correct
35	Correct	21 ms	145360 KB	Output is correct
36	Correct	41 ms	145232 KB	Output is correct
37	Correct	32 ms	145236 KB	Output is correct
38	Correct	25 ms	145244 KB	Output is correct
39	Correct	31 ms	145240 KB	Output is correct
40	Correct	35 ms	145236 KB	Output is correct
41	Correct	25 ms	145240 KB	Output is correct
42	Correct	23 ms	145416 KB	Output is correct
43	Correct	25 ms	145296 KB	Output is correct
44	Correct	22 ms	145244 KB	Output is correct
45	Correct	25 ms	145304 KB	Output is correct
46	Correct	23 ms	145316 KB	Output is correct
47	Correct	25 ms	145236 KB	Output is correct
48	Correct	26 ms	145364 KB	Output is correct
49	Correct	26 ms	145428 KB	Output is correct
50	Correct	23 ms	145232 KB	Output is correct
51	Correct	24 ms	145244 KB	Output is correct
52	Correct	22 ms	145292 KB	Output is correct
53	Correct	23 ms	145244 KB	Output is correct
54	Correct	22 ms	145348 KB	Output is correct
55	Correct	24 ms	145244 KB	Output is correct
56	Correct	22 ms	145244 KB	Output is correct
57	Correct	25 ms	145444 KB	Output is correct
58	Correct	23 ms	145444 KB	Output is correct
59	Correct	49 ms	145236 KB	Output is correct
60	Correct	32 ms	145236 KB	Output is correct
61	Correct	48 ms	145420 KB	Output is correct
62	Correct	33 ms	145232 KB	Output is correct
63	Correct	49 ms	145416 KB	Output is correct
64	Correct	35 ms	145488 KB	Output is correct
65	Correct	43 ms	145428 KB	Output is correct
66	Correct	41 ms	145244 KB	Output is correct
67	Correct	41 ms	145240 KB	Output is correct
68	Correct	40 ms	145448 KB	Output is correct
69	Correct	42 ms	145240 KB	Output is correct
70	Correct	45 ms	145240 KB	Output is correct
71	Correct	40 ms	145244 KB	Output is correct
72	Correct	47 ms	145244 KB	Output is correct
73	Correct	37 ms	145244 KB	Output is correct
74	Correct	41 ms	145232 KB	Output is correct
75	Correct	38 ms	145496 KB	Output is correct
76	Correct	47 ms	145244 KB	Output is correct
77	Correct	45 ms	145244 KB	Output is correct
78	Correct	42 ms	145496 KB	Output is correct
79	Correct	39 ms	145232 KB	Output is correct
80	Correct	46 ms	145244 KB	Output is correct
81	Correct	37 ms	145328 KB	Output is correct
82	Correct	38 ms	145244 KB	Output is correct
83	Correct	47 ms	145244 KB	Output is correct
84	Correct	43 ms	145748 KB	Output is correct
85	Correct	41 ms	145240 KB	Output is correct
86	Correct	42 ms	145424 KB	Output is correct
87	Correct	41 ms	145244 KB	Output is correct
88	Correct	54 ms	145428 KB	Output is correct
89	Correct	48 ms	145280 KB	Output is correct
90	Correct	36 ms	145492 KB	Output is correct
91	Correct	50 ms	145232 KB	Output is correct
92	Correct	49 ms	145428 KB	Output is correct
93	Correct	38 ms	145288 KB	Output is correct

답안 #888072

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 10.0 / 10.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
10.0 / 10.0

Subtask #4
75.0 / 75.0