Submission #244944

#	Time	Username	Problem	Language	Result	Execution time	Memory
244944		maximath_1	Collecting Stamps 3 (JOI20_ho_t3)	C++11	15 / 100	89 ms	65424 KiB

ho_t3

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

const int inf = 2e9 + 69;
int x[205], t[205], n, l, dp[205][205][205][2];

int main(){
	scanf("%d%d", &n, &l);
	for(int i = 1; i <= n; i ++) scanf("%d", &x[i]);
	for(int i = 1; i <= n; i ++) scanf("%d", &t[i]);
	x[n + 1] = l;
	
	for(int i = 0; i <= n; i ++) for(int j = 0; j <= n; j ++) for(int k = 0; k <= n; k ++) for(int a = 0; a < 2; a ++)
		dp[i][j][k][a] = inf + 5;
	dp[0][0][0][0] = dp[0][0][0][1] = 0;

	for(int i = 0; i < n; i ++) for(int j = 0; i + j < n; j ++) for(int k = 0; k <= i + j; k ++){
		int tim;
		if(dp[i][j][k][0] < inf){
			tim = dp[i][j][k][0] + x[i + 1] - x[i];
			dp[i + 1][j][k + (t[i + 1] >= tim)][0] = min(dp[i + 1][j][k + (t[i + 1] >= tim)][0], tim);

			tim = dp[i][j][k][0] + x[i] + l - x[n - j];
			dp[i][j + 1][k + (t[n - j] >= tim)][1] = min(dp[i][j + 1][k + (t[n - j] >= tim)][1], tim);
		}

		if(dp[i][j][k][1] < inf){
			tim = dp[i][j][k][1] + x[n - j + 1] - x[n -j];
			dp[i][j + 1][k + (t[n - j] >= tim)][1] = min(dp[i][j + 1][k + (t[n - j] >= tim)][1], tim);

			tim = dp[i][j][k][1] + l - x[n - j + 1] + x[i + 1];
			dp[i + 1][j][k + (t[i + 1] >= tim)][0] = min(dp[i + 1][j][k + (t[i + 1] >= tim)][0], tim);
		}
	}

	int ans = 0;
	for(int i = 0; i <= n; i ++) for(int j = 0; i + j <= n; j ++) for(int k = 0; k <= i + j; k ++){
		if(min(dp[i][j][k][0], dp[i][j][k][1]) < inf)
			ans = max(ans, k);
	}

	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

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

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