oj.uz

Submission #871201

# Submission time Handle Problem Language Result Execution time Memory
871201 2023-11-10T08:50:06 Z goodspeed0208 Collecting Stamps 3 (JOI20_ho_t3) C++14
5 / 100
 97 ms 67940 KB 
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
//讀: 5 想1~3: 8min 實作40min 
int dp[205][205][2][205];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(dp, -1, sizeof(dp));
	int n, l;
	cin >> n >> l;
	vector<int>x(n+1), t(n+1);
	x[0] = t[0] = 0;
	for (int i = 1 ; i <= n ; i++) cin >> x[i];
	for (int i = 1 ; i <= n ; i++) cin >> t[i];
	dp[0][0][0][0] = dp[0][0][1][0] = 0;
	n++;
	int ans= 0;
	for (int k = 0 ; k <= 200 ; k++) {//time
		for (int i = 0 ; i < n ; i++) {//left
			for (int j = n-1 ; j >= 0 ; j--) {//right
				for (int p = 0 ; p <= 1 ; p++) {
					if (dp[i][j][p][k] == -1) {
						continue;
					}
					if ((i + 1) % n == j) {
						//cout << i << " " << j << " " << p << " " << k << " " << dp[i][j][p][k] << "\n";
						if (dp[i][j][p][k] > ans)ans = dp[i][j][p][k];
						continue;
					}
					//cout << i << " " << j << " " << p << " " << k << " " << dp[i][j][p][k] << "\n";
					//if (i + 1 == j) ans = max(ans, dp[i][j][p][k]);
					int pos = (p == 0 ? x[i] : x[j]), next;
					next = (i+1);
					int cost = k + (x[next] - pos + l) % l;
					dp[next][j][0][cost] = max(dp[next][j][0][cost], dp[i][j][p][k] + (cost <= t[next]));
					/*if (dp[next][j][0][cost] > 0) {
						cout << next << " " << j << " " << 0 << " " << cost << "\n";
						return 0;
					}*/
					next = (j==0 ? n-1 : j-1); 
					cost = k + (pos - x[next] + l) % l;
					dp[i][next][1][cost] = max(dp[i][next][1][cost], dp[i][j][p][k] + (cost <= t[next]));
					/*if (dp[i][next][1][cost] > 0) {
						cout << i << " " << next << " " << 1 << " " << cost << "\n";
						return 0;
					}*/
				} 
			}
		}			
	}
	cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67828 KB Output is correct
2 Correct 9 ms 67676 KB Output is correct
3 Correct 9 ms 67800 KB Output is correct
4 Correct 8 ms 67768 KB Output is correct
5 Correct 8 ms 67676 KB Output is correct
6 Correct 9 ms 67684 KB Output is correct
7 Correct 9 ms 67680 KB Output is correct
8 Correct 9 ms 67804 KB Output is correct
9 Correct 9 ms 67904 KB Output is correct
10 Correct 8 ms 67684 KB Output is correct
11 Correct 8 ms 67744 KB Output is correct
12 Correct 9 ms 67684 KB Output is correct
13 Correct 9 ms 67688 KB Output is correct
14 Correct 10 ms 67892 KB Output is correct
15 Correct 9 ms 67688 KB Output is correct
16 Correct 9 ms 67804 KB Output is correct
17 Correct 9 ms 67940 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67828 KB Output is correct
2 Correct 9 ms 67676 KB Output is correct
3 Correct 9 ms 67800 KB Output is correct
4 Correct 8 ms 67768 KB Output is correct
5 Correct 8 ms 67676 KB Output is correct
6 Correct 9 ms 67684 KB Output is correct
7 Correct 9 ms 67680 KB Output is correct
8 Correct 9 ms 67804 KB Output is correct
9 Correct 9 ms 67904 KB Output is correct
10 Correct 8 ms 67684 KB Output is correct
11 Correct 8 ms 67744 KB Output is correct
12 Correct 9 ms 67684 KB Output is correct
13 Correct 9 ms 67688 KB Output is correct
14 Correct 10 ms 67892 KB Output is correct
15 Correct 9 ms 67688 KB Output is correct
16 Correct 9 ms 67804 KB Output is correct
17 Correct 9 ms 67940 KB Output is correct
18 Incorrect 9 ms 67688 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67828 KB Output is correct
2 Correct 9 ms 67676 KB Output is correct
3 Correct 9 ms 67800 KB Output is correct
4 Correct 8 ms 67768 KB Output is correct
5 Correct 8 ms 67676 KB Output is correct
6 Correct 9 ms 67684 KB Output is correct
7 Correct 9 ms 67680 KB Output is correct
8 Correct 9 ms 67804 KB Output is correct
9 Correct 9 ms 67904 KB Output is correct
10 Correct 8 ms 67684 KB Output is correct
11 Correct 8 ms 67744 KB Output is correct
12 Correct 9 ms 67684 KB Output is correct
13 Correct 9 ms 67688 KB Output is correct
14 Correct 10 ms 67892 KB Output is correct
15 Correct 9 ms 67688 KB Output is correct
16 Correct 9 ms 67804 KB Output is correct
17 Correct 9 ms 67940 KB Output is correct
18 Correct 97 ms 67876 KB Output is correct
19 Correct 58 ms 67896 KB Output is correct
20 Correct 35 ms 67888 KB Output is correct
21 Correct 61 ms 67932 KB Output is correct
22 Correct 68 ms 67880 KB Output is correct
23 Correct 28 ms 67684 KB Output is correct
24 Correct 23 ms 67684 KB Output is correct
25 Correct 28 ms 67936 KB Output is correct
26 Correct 14 ms 67684 KB Output is correct
27 Correct 30 ms 67684 KB Output is correct
28 Correct 22 ms 67684 KB Output is correct
29 Correct 33 ms 67896 KB Output is correct
30 Correct 24 ms 67688 KB Output is correct
31 Incorrect 27 ms 67684 KB Output isn't correct
32 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 67828 KB Output is correct
2 Correct 9 ms 67676 KB Output is correct
3 Correct 9 ms 67800 KB Output is correct
4 Correct 8 ms 67768 KB Output is correct
5 Correct 8 ms 67676 KB Output is correct
6 Correct 9 ms 67684 KB Output is correct
7 Correct 9 ms 67680 KB Output is correct
8 Correct 9 ms 67804 KB Output is correct
9 Correct 9 ms 67904 KB Output is correct
10 Correct 8 ms 67684 KB Output is correct
11 Correct 8 ms 67744 KB Output is correct
12 Correct 9 ms 67684 KB Output is correct
13 Correct 9 ms 67688 KB Output is correct
14 Correct 10 ms 67892 KB Output is correct
15 Correct 9 ms 67688 KB Output is correct
16 Correct 9 ms 67804 KB Output is correct
17 Correct 9 ms 67940 KB Output is correct
18 Incorrect 9 ms 67688 KB Output isn't correct
19 Halted 0 ms 0 KB -