Submission #535483

#	Time	Username	Problem	Language	Result	Execution time	Memory
535483		EJam	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	199 ms	135316 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

const int N = 205;
const ll INF = 1e18;
ll dp[N][N][N][2];

void tkmin(ll &a, ll b) { a = min(a, b); }
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				dp[i][j][k][0] = INF;
				dp[i][j][k][1] = INF;
			}
		}
	}

	int n, l; cin >> n >> l;
	vll v(n);
	vll t(n);
	for (auto &it: v) cin>>it;
	for (auto &it: t) cin>>it;

	vll v2 = v;
	reverse(v2.begin(), v2.end());
	for (auto &it: v2) it = l-it;
	v.insert(v.begin(), 0);
	v2.insert(v2.begin(), 0);

	vll t2 = t;
	reverse(t2.begin(), t2.end());
	t.insert(t.begin(), 0);
	t2.insert(t2.begin(), 0);

	dp[0][0][0][0] = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j+i < n; j++) {
			for (int cnt = 0; cnt < n; cnt++) {
				// right side
				ll cur = dp[i][j][cnt][0];

				ll dist = v[i+1] - v[i];
				ll ncnt = cnt;
				if (cur + dist <= t[i+1]) ncnt++;
				tkmin(dp[i+1][j][ncnt][0], cur + dist);

				dist = v2[j+1] + v[i];
				ncnt = cnt;
				if (cur + dist <= t2[j+1]) ncnt++;
				tkmin(dp[i][j+1][ncnt][1], cur + dist);

				// at left side
				cur = dp[i][j][cnt][1];

				dist = v2[j+1] - v2[j];
				ncnt = cnt;
				if (cur + dist <= t2[j+1]) ncnt++;
//				if (cnt == 4 && i == 2 && j == 2) cout << ncnt << ' ' << dp[i][j+1][ncnt][1] << '\n';
				tkmin(dp[i][j+1][ncnt][1], cur + dist);
//				if (cnt == 4 && i == 2 && j == 2) cout << dp[i][j+1][ncnt][1] << '\n';

				dist = v2[j] + v[i+1];
				ncnt = cnt;
				if (cur + dist <= t[i+1]) ncnt++;
				tkmin(dp[i+1][j][ncnt][0], cur + dist);
			}
		}
	}

	ll ans = 0;
	for (int cnt = 0; cnt <= n; cnt++) {
//		cout << cnt <<": \n";
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j+i <= n; j++) {
//				auto p = [] (ll x) { return x >= INF? -1: x; };
//				cout << p(dp[i][j][cnt][0]) << ":" << p(dp[i][j][cnt][1]) << ' ';
				if (dp[i][j][cnt][0] != INF || dp[i][j][cnt][1] != INF) ans = cnt;
			}
//			cout << '\n';
		}
//		cout << '\n';
	}
	cout << ans << '\n';


	return 0;
}

/*
alias csafe='g++ -std=c++17 -Wshadow -Wall -DLOCAL -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g'
*/

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