Submission #707727

#	Time	Username	Problem	Language	Result	Execution time	Memory
707727		rainboy	Collecting Stamps 3 (JOI20_ho_t3)	C11	100 / 100	93 ms	65160 KiB

ho_t3

#include <stdio.h>

#define N	200
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }

int dist(int m, int a, int b) {
	int tmp;

	if (a > b)
		tmp = a, a = b, b = tmp;
	return min(b - a, m + a - b);
}

int main() {
	static int xx[N], tt[N];
	static long long dp[N + 1][N + 1][N + 1][2];
	int n, m, i, j, k, k_, s;

	scanf("%d%d", &n, &m);
	for (i = 0; i < n; i++)
		scanf("%d", &xx[i]);
	for (i = 0; i < n; i++)
		scanf("%d", &tt[i]);
	for (i = 0; i <= n; i++)
		for (j = i; j <= n; j++)
			for (k = 0; k <= n; k++)
				for (s = 0; s < 2; s++)
					dp[i][j][k][s] = INF;
	dp[0][n][0][0] = 0;
	for (i = 0; i <= n; i++)
		for (j = n; j > i; j--)
			for (k = 0; k <= n; k++)
				for (s = 0; s < 2; s++) {
					long long t = dp[i][j][k][s], t_;
					int x = s == 0 ? (i == 0 ? 0 : xx[i - 1]) : (j == n ? 0 : xx[j]);

					if (t == INF)
						continue;
					k_ = k, t_ = t + dist(m, x, xx[i]);
					if (t_ <= tt[i])
						k_++;
					dp[i + 1][j][k_][0] = min(dp[i + 1][j][k_][0], t_);
					k_ = k, t_ = t + dist(m, x, xx[j - 1]);
					if (t_ <= tt[j - 1])
						k_++;
					dp[i][j - 1][k_][1] = min(dp[i][j - 1][k_][1], t_);
				}
	k_ = 0;
	for (i = 0; i <= n; i++)
		for (k = 0; k <= n; k++)
			if (dp[i][i][k][0] != INF || dp[i][i][k][1] != INF)
				k_ = max(k_, k);
	printf("%d\n", k_);
	return 0;
}

Compilation message (stderr)

ho_t3.c: In function 'main':
ho_t3.c:22:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d%d", &n, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~
ho_t3.c:24:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |   scanf("%d", &xx[i]);
      |   ^~~~~~~~~~~~~~~~~~~
ho_t3.c:26:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |   scanf("%d", &tt[i]);
      |   ^~~~~~~~~~~~~~~~~~~

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