oj.uz

답안 #871199

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
871199 2023-11-10T08:46:36 Z goodspeed0208 Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 9 ms 67676 KB 
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
//讀: 5 想1~3: 8min 
int dp[205][205][2][205];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	memset(dp, -1, sizeof(dp));
	//cout << dp[1][1][1][1] << "\n";
	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 == 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
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 67672 KB Output is correct
2 Correct 9 ms 67672 KB Output is correct
3 Incorrect 9 ms 67676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 67672 KB Output is correct
2 Correct 9 ms 67672 KB Output is correct
3 Incorrect 9 ms 67676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 67672 KB Output is correct
2 Correct 9 ms 67672 KB Output is correct
3 Incorrect 9 ms 67676 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 67672 KB Output is correct
2 Correct 9 ms 67672 KB Output is correct
3 Incorrect 9 ms 67676 KB Output isn't correct
4 Halted 0 ms 0 KB -