Submission #201231

#	Time	Username	Problem	Language	Result	Execution time	Memory
201231		ainta	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	83 ms	132344 KiB

ho_t3

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n;
long long X[410], Left[410][410][410], Right[410][410][410], T[410], L;
int main() {
	int i, j, k;
	scanf("%d%lld", &n, &L);
	for (i = n + 1; i <= n + n; i++) scanf("%lld", &X[i]);
	for (i = n + 1; i <= n + n; i++) scanf("%lld", &T[i]);
	for (i = 0; i < n; i++) {
		X[i] = X[n + 1 + i] - L;
		T[i] = T[n + 1 + i];
	}
	for (i = n; i >= 0; i--) {
		for (j = n - i; j <= n; j++) {
			int b = j, e = j + i;
			for (k = 0; k <= n; k++)Left[b][e][k] = Right[b][e][k] = -1e18;
			Left[b][e][0] = Right[b][e][0] = 1e18;
			for (k = 1; k <= n - i; k++) {
				long long t1 = max(min(Left[b - 1][e][k - 1], T[b - 1]), Left[b - 1][e][k]) - (X[b] - X[b - 1]);
				long long t2 = max(min(Right[b][e + 1][k - 1], T[e + 1]), Right[b][e + 1][k]) - (X[e + 1] - X[b]);
				if (max(t1, t2) >= 0)Left[b][e][k] = max(t1, t2);
				t1 = max(min(Left[b - 1][e][k - 1], T[b - 1]), Left[b - 1][e][k]) - (X[e] - X[b - 1]);
				t2 = max(min(Right[b][e + 1][k - 1], T[e + 1]), Right[b][e + 1][k]) - (X[e + 1] - X[e]);
				if (max(t1, t2) >= 0)Right[b][e][k] = max(t1, t2);
			}
		}
	}
	int res = 0;
	for (i = 1; i <= n; i++)if (Left[n][n][i] >= 0 || Right[n][n][i]>=0)res = i;
	printf("%d\n", res);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:9:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &n, &L);
  ~~~~~^~~~~~~~~~~~~~~~~~
ho_t3.cpp:10:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = n + 1; i <= n + n; i++) scanf("%lld", &X[i]);
                                   ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:11:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = n + 1; i <= n + n; i++) scanf("%lld", &T[i]);
                                   ~~~~~^~~~~~~~~~~~~~~

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