Submission #244949

#	Time	Username	Problem	Language	Result	Execution time	Memory
244949		maximath_1	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	136 ms	135288 KiB

ho_t3

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

const ll inf = 1e18;
ll x[205], t[205], l, dp[205][205][205][2];
int n;

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

	for(int i = 0; i < n; i ++) for(int j = 0; i + j < n; j ++) for(int k = 0; k <= i + j; k ++){
		ll 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:10: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:11: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("%lld", &x[i]);
                               ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:12: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("%lld", &t[i]);
                               ~~~~~^~~~~~~~~~~~~~~

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