제출 #647395

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
647395		beaconmc	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	138 ms	127440 KiB

ho_t3

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;


#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)

#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll n,l;
ll dp[201][201][201][2];

int main(){
	cin >> n >> l;
	vector<ll> dists(n+1);
	vector<ll> times(n+1);
	FOR(i,1,n+1) cin >> dists[i];
	FOR(i,1,n+1) cin >> times[i];
	FOR(i,0,201){
		FOR(j,0,201){
			FOR(k,0,201){
				dp[i][j][k][0] = 10000000000000;
				dp[i][j][k][1] = 10000000000000;
			}
		}
	}

	dp[n][0][0][1] = 0;
	dp[n][1][0][1] = dists[1];
	if (times[1] >= dists[1]) dp[n][1][1][1] = dists[1];



	// if (times[n] >= l-places[n]) dp[n][1][1][0] = l-places[n];
	// else dp[n][1][0][0] = l-places[n];

	// if (times[1] >= places[1]) dp[n][1][1][1] = places[1];
	// else dp[n][1][0][1] = places[1];

	FOR(k,0,n+1) FORNEG(i,n,-1) FOR(j,0,n+1){
		if (i<j) continue;


		if (i!=n){
			dp[i][j][k][0] = min(dp[i][j][k][0], dp[i+1][j][k][0] + dists[i+1] - dists[i]);

			if (k!=0){
				ll tm = dists[i+1] - dists[i] + dp[i+1][j][k-1][0];

				if (tm <= times[i]){
					dp[i][j][k][0] = min(dp[i][j][k][0], tm);
				}
			}

			dp[i][j][k][1] = min(dp[i][j][k][1], dp[i+1][j][k][0] + l + dists[j] - dists[i+1]);

			if (k!=0){
				ll tm = dp[i+1][j][k-1][0] + l + dists[j] - dists[i+1];

				if (tm <= times[j]){
					dp[i][j][k][1] = min(dp[i][j][k][1], tm);
				}
			}

		}

		if (j!=0){
			dp[i][j][k][1] = min(dp[i][j][k][1], dp[i][j-1][k][1] + dists[j] - dists[j-1]);

			if (k!=0){
				ll tm = dists[j] - dists[j-1] +  dp[i][j-1][k-1][1];

				if (tm <= times[j]){
					dp[i][j][k][1] = min(dp[i][j][k][1], tm);
				}
			}
			dp[i][j][k][0] = min(dp[i][j][k][0], dp[i][j-1][k][1] + l + dists[j-1] - dists[i]);

			if (k!=0){
				ll tm = dp[i][j-1][k-1][1] + l + dists[j-1] - dists[i];

				if (tm <= times[i]){
					dp[i][j][k][0] = min(dp[i][j][k][0], tm);
				}
			}

		}

	}


	ll ans = 0;

	FOR(i,0,201) FOR(j,0,201) FOR(k,0,201) FOR(m,0,2){

		if (dp[i][j][k][m] < 10000000000000) ans = max(ans, k);
	}

	// if (ans==7){

	// 	cout << n << " " << l << endl;
	// 	FOR(i,0,n+1) cout << dists[i] << " ";
	// 	cout << endl;
	// 	FOR(i,0,n+1) cout << times[i] << " ";
	// }
	// else cout << ans;
	cout << ans;


}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75