Submission #363883

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
363883	2021-02-07T12:46:42 Z	wind_reaper	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	384 KB

ho_t3

#include <bits/stdc++.h>

using namespace std;

const int64_t INF = 1e16;

template<typename T> 
void smin(T &a, T b){
	a = min(a, b);
}
int32_t main(){
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL); 
	
	int n; 
	int64_t l; 
	cin >> n >> l; 

	vector<int64_t> pos(n+2), t(n+2);

	for(int i = 1; i <= n; i++)
		cin >> pos[i];

	for(int i = 1; i <= n; i++)
		cin >> t[i];

	t[0] = 0;
	pos[0] = 0;
	pos[n+1] = l;
	t[n+1] = 0; 
	int64_t dp[n+2][n+2][2][n+2];
	for(int i = 0; i < n + 2; i++)
		for(int j = 0; j < n + 2; j++)
			for(int k = 0; k < n + 2; k++)
				dp[i][j][0][k] = dp[i][j][1][k] = INF; 

	dp[0][n+1][0][0] = dp[0][n+1][1][0] = 0;
	for(int i = 0; i <= n; i++){
		for(int j = n+1; j > i; --j){
			for(int k = 0; k <= n; k++){
				int64_t min_time = min(dp[i][j][0][k]+pos[i+1]-pos[i], dp[i][j][1][k]+l-pos[j]+pos[i+1]);
				smin(dp[i+1][j][0][k+(min_time<=t[i+1] ? 1 : 0)], min_time);
				min_time = min(dp[i][j][0][k]+l-pos[j-1]+pos[i], dp[i][j][1][k]+pos[j]-pos[j-1]);
				smin(dp[i][j-1][1][k+(min_time<=t[j-1] ? 1 : 0)], min_time);
			}
		}
	}

	int ans = 0; 
	for(int i = 0; i <= n+1; i++)
		for(int j = 0; j <= n+1; j++)
			for(int k = 0; k <= n+1; k++)
				for(int z = 0; z < 2; z++)
					if(dp[i][j][z][k] < INF){
						ans = max(ans, k);
					}

	cout << ans << '\n';
	return 0; 
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 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	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Incorrect	1 ms	364 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 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	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Incorrect	1 ms	364 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #3

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 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	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Incorrect	1 ms	364 KB	Output isn't correct
17	Halted	0 ms	0 KB	-

Subtask #4

0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	1 ms	364 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	364 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct
16	Incorrect	1 ms	364 KB	Output isn't correct
17	Halted	0 ms	0 KB	-