Submission #201557

#	Time	Username	Problem	Language	Result	Execution time	Memory
201557		abacaba	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	165 ms	78328 KiB

ho_t3

#include <bits/stdc++.h> 
using namespace std;

#define f first
#define se second

template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}

template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int inf = 0x3f3f3f3f;
const int N = 2e2 + 15;
int n, x, dp[2][N][N][N], ans;
pair <int, int> a[N];

// dp[last][l][r][items_taken] = min_time

inline int get(int c, int d) {
	return min({abs(a[c].f - a[d].f), abs(a[c].f + x - a[d].f), abs(a[d].f + x - a[c].f)});
}

inline void calc(int l, int r, int len) {
	// FROM L
	int nxt = (l - 1 + n) % n;
	int d = get(l, nxt);
	if(nxt != r) {
		for(int k = 0; k <= len; ++k) {
			if(dp[0][l][r][k] + d <= a[nxt].se)
				Min(dp[0][nxt][r][k+1], dp[0][l][r][k] + d);
			else
				Min(dp[0][nxt][r][k], dp[0][l][r][k] + d);
		}
	}
	nxt = (r + 1 + n) % n;
	if(nxt != l) {
		d = get(l, nxt);
		for(int k = 0; k <= len; ++k) {
			if(dp[0][l][r][k] + d <= a[nxt].se)
				Min(dp[1][l][nxt][k+1], dp[0][l][r][k] + d);
			else
				Min(dp[1][l][nxt][k], dp[0][l][r][k] + d);
		}
	}

	// FROM R
	nxt = (l - 1 + n) % n;
	if(nxt != r) {
		d = get(r, nxt);
		for(int k = 0; k <= len; ++k) {
			if(dp[1][l][r][k] + d <= a[nxt].se)
				Min(dp[0][nxt][r][k+1], dp[1][l][r][k] + d);
			else
				Min(dp[0][nxt][r][k], dp[1][l][r][k] + d);
		}
	}
	nxt = (r + 1 + n) % n;
	if(nxt != l) {
		d = get(r, nxt);
		for(int k = 0; k <= len; ++k) {
			if(dp[1][l][r][k] + d <= a[nxt].se)
				Min(dp[1][l][nxt][k+1], dp[1][l][r][k] + d);
			else
				Min(dp[1][l][nxt][k], dp[1][l][r][k] + d);
		}
	}
}

main() {
	memset(dp, 0x3f, sizeof(dp));
	cin >> n >> x;
	for(int i = 1; i <= n; ++i)
		cin >> a[i].f;
	for(int i = 1; i <= n; ++i)
		cin >> a[i].se;
	reverse(a + 1, a + 1 + n);
	++n;
	dp[0][0][0][0] = 0;
	for(int len = 0; len < n; ++len) {
		for(int l = 0; l < n; ++l) {
			int r = (l + len - 1) % n;
			calc(l, r, len);
		}
	}
	for(int k = n; k >= 0; --k)
		for(int i = 0; i < 2; ++i)
			for(int l = 0; l < n; ++l)
				for(int r = 0; r < n; ++r)
					if(dp[i][l][r][k] != inf) {
						cout << k << endl;
						return 0;
					}
	return 0;
}

Compilation message (stderr)

ho_t3.cpp:72:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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