답안 #707554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707554	2023-03-09T09:10:20 Z	Dan4Life	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	97 ms	145292 KB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define int long long
#define sz(a) (int)a.size()
const int mxN = (int)2e2+10;
const int LINF = (int)2e18;
int dp[mxN][mxN][mxN][2];
int x[mxN], t[mxN];
//dp[pref][suf][]
int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int n, L; cin >> n >> L; int ans = 0;
	for(int i = 1; i <= n; i++) cin >> x[i], x[n+i+1]=x[i];
	for(int i = 1; i <= n; i++) cin >> t[i], t[n+i+1]=t[i];
	for(int i = 0; i < mxN; i++)
		for(int j = 0; j < mxN; j++)
			for(int k = 0; k < mxN; k++)
				for(int l = 0; l < 2; l++)
					dp[i][j][k][l] = LINF;
	dp[n+1][n+1][0][0]=dp[n+1][n+1][0][1]=0;
	//0 1 2 3 4 5 6 
	t[n+1] = -LINF;
	for(int len = 2; len <= n+1; len++){
		for(int l = 1; l <= n+1; l++){
			for(int k = 0; k <= n; k++){
				int r = l+len-1;
				dp[l][r][k][0] = min({ dp[l][r][k][0],
					dp[l+1][r][k][0]+min(abs(x[l+1]-x[l]),L-abs(x[l+1]-x[l])),
					dp[l+1][r][k][1]+min(abs(x[r]-x[l]),L-abs(x[r]-x[l]))
				});
				dp[l][r][k][1] = min({ dp[l][r][k][1],
					dp[l][r-1][k][0]+min(abs(x[l]-x[r]),L-abs(x[l]-x[r])),
					dp[l][r-1][k][1]+min(abs(x[r-1]-x[r]),L-abs(x[r-1]-x[r]))
				});
				if(k){
					int tm = abs(x[l+1]-x[l]); tm=min(tm,L-tm); tm+=dp[l+1][r][k-1][0];
					if(tm<=t[l]) dp[l][r][k][0] = min(dp[l][r][k][0], tm);
					tm = abs(x[r]-x[l]); tm=min(tm,L-tm); tm+=dp[l+1][r][k-1][1];
					if(tm<=t[l]) dp[l][r][k][0] = min(dp[l][r][k][0], tm);
					tm = abs(x[l]-x[r]); tm=min(tm,L-tm); tm+=dp[l][r-1][k-1][0];
					if(tm<=t[r]) dp[l][r][k][1] = min(dp[l][r][k][1],tm);
					tm = abs(x[r-1]-x[r]); tm=min(tm,L-tm); tm+=dp[l][r-1][k-1][1];
					if(tm<=t[r]) dp[l][r][k][1] = min(dp[l][r][k][1],tm);
				}
				if(len==n+1 and (dp[l][r][k][0]<LINF or dp[l][r][k][1]<LINF)) ans = max(ans, k);
			}
		}
	}

	cout << ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	145240 KB	Output is correct
2	Correct	57 ms	145228 KB	Output is correct
3	Correct	56 ms	145224 KB	Output is correct
4	Correct	58 ms	145224 KB	Output is correct
5	Correct	55 ms	145228 KB	Output is correct
6	Correct	57 ms	145164 KB	Output is correct
7	Correct	57 ms	145176 KB	Output is correct
8	Correct	56 ms	145276 KB	Output is correct
9	Correct	58 ms	145228 KB	Output is correct
10	Correct	58 ms	145196 KB	Output is correct
11	Correct	59 ms	145264 KB	Output is correct
12	Correct	59 ms	145292 KB	Output is correct
13	Correct	58 ms	145256 KB	Output is correct
14	Correct	57 ms	145260 KB	Output is correct
15	Correct	57 ms	145264 KB	Output is correct
16	Correct	57 ms	145204 KB	Output is correct
17	Correct	56 ms	145216 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	145240 KB	Output is correct
2	Correct	57 ms	145228 KB	Output is correct
3	Correct	56 ms	145224 KB	Output is correct
4	Correct	58 ms	145224 KB	Output is correct
5	Correct	55 ms	145228 KB	Output is correct
6	Correct	57 ms	145164 KB	Output is correct
7	Correct	57 ms	145176 KB	Output is correct
8	Correct	56 ms	145276 KB	Output is correct
9	Correct	58 ms	145228 KB	Output is correct
10	Correct	58 ms	145196 KB	Output is correct
11	Correct	59 ms	145264 KB	Output is correct
12	Correct	59 ms	145292 KB	Output is correct
13	Correct	58 ms	145256 KB	Output is correct
14	Correct	57 ms	145260 KB	Output is correct
15	Correct	57 ms	145264 KB	Output is correct
16	Correct	57 ms	145204 KB	Output is correct
17	Correct	56 ms	145216 KB	Output is correct
18	Correct	60 ms	145260 KB	Output is correct
19	Correct	57 ms	145220 KB	Output is correct
20	Correct	64 ms	145272 KB	Output is correct
21	Correct	56 ms	145232 KB	Output is correct
22	Correct	61 ms	145176 KB	Output is correct
23	Correct	57 ms	145176 KB	Output is correct
24	Correct	56 ms	145220 KB	Output is correct
25	Correct	56 ms	145228 KB	Output is correct
26	Correct	58 ms	145280 KB	Output is correct
27	Correct	57 ms	145224 KB	Output is correct
28	Correct	58 ms	145228 KB	Output is correct
29	Correct	60 ms	145212 KB	Output is correct
30	Correct	56 ms	145232 KB	Output is correct
31	Correct	59 ms	145204 KB	Output is correct
32	Correct	59 ms	145244 KB	Output is correct
33	Correct	58 ms	145292 KB	Output is correct
34	Correct	67 ms	145180 KB	Output is correct
35	Correct	55 ms	145240 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	145240 KB	Output is correct
2	Correct	57 ms	145228 KB	Output is correct
3	Correct	56 ms	145224 KB	Output is correct
4	Correct	58 ms	145224 KB	Output is correct
5	Correct	55 ms	145228 KB	Output is correct
6	Correct	57 ms	145164 KB	Output is correct
7	Correct	57 ms	145176 KB	Output is correct
8	Correct	56 ms	145276 KB	Output is correct
9	Correct	58 ms	145228 KB	Output is correct
10	Correct	58 ms	145196 KB	Output is correct
11	Correct	59 ms	145264 KB	Output is correct
12	Correct	59 ms	145292 KB	Output is correct
13	Correct	58 ms	145256 KB	Output is correct
14	Correct	57 ms	145260 KB	Output is correct
15	Correct	57 ms	145264 KB	Output is correct
16	Correct	57 ms	145204 KB	Output is correct
17	Correct	56 ms	145216 KB	Output is correct
18	Incorrect	97 ms	145172 KB	Output isn't correct
19	Halted	0 ms	0 KB	-

Subtask #4
0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	56 ms	145240 KB	Output is correct
2	Correct	57 ms	145228 KB	Output is correct
3	Correct	56 ms	145224 KB	Output is correct
4	Correct	58 ms	145224 KB	Output is correct
5	Correct	55 ms	145228 KB	Output is correct
6	Correct	57 ms	145164 KB	Output is correct
7	Correct	57 ms	145176 KB	Output is correct
8	Correct	56 ms	145276 KB	Output is correct
9	Correct	58 ms	145228 KB	Output is correct
10	Correct	58 ms	145196 KB	Output is correct
11	Correct	59 ms	145264 KB	Output is correct
12	Correct	59 ms	145292 KB	Output is correct
13	Correct	58 ms	145256 KB	Output is correct
14	Correct	57 ms	145260 KB	Output is correct
15	Correct	57 ms	145264 KB	Output is correct
16	Correct	57 ms	145204 KB	Output is correct
17	Correct	56 ms	145216 KB	Output is correct
18	Correct	60 ms	145260 KB	Output is correct
19	Correct	57 ms	145220 KB	Output is correct
20	Correct	64 ms	145272 KB	Output is correct
21	Correct	56 ms	145232 KB	Output is correct
22	Correct	61 ms	145176 KB	Output is correct
23	Correct	57 ms	145176 KB	Output is correct
24	Correct	56 ms	145220 KB	Output is correct
25	Correct	56 ms	145228 KB	Output is correct
26	Correct	58 ms	145280 KB	Output is correct
27	Correct	57 ms	145224 KB	Output is correct
28	Correct	58 ms	145228 KB	Output is correct
29	Correct	60 ms	145212 KB	Output is correct
30	Correct	56 ms	145232 KB	Output is correct
31	Correct	59 ms	145204 KB	Output is correct
32	Correct	59 ms	145244 KB	Output is correct
33	Correct	58 ms	145292 KB	Output is correct
34	Correct	67 ms	145180 KB	Output is correct
35	Correct	55 ms	145240 KB	Output is correct
36	Incorrect	97 ms	145172 KB	Output isn't correct
37	Halted	0 ms	0 KB	-

답안 #707554

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 10.0

Subtask #4 0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 10.0

Subtask #4
0 / 75.0