Submission #871201

#	Time	Username	Problem	Language	Result	Execution time	Memory
871201		goodspeed0208	Collecting Stamps 3 (JOI20_ho_t3)	C++14	5 / 100	97 ms	67940 KiB

ho_t3

#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 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75