Submission #244907

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

ho_t3

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

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

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[0] = 0; 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 ++)
		dpcw[i][j][k] = dpccw[i][j][k] = inf;

	dpcw[0][0][0] = 0;
	for(int tim, i = 0; i < n; i ++) for(int j = 0; i + j < n; j ++) for(int k = 0; k <= i + j; k ++){
		if(dpcw[i][j][k] < inf){
			tim = dpcw[i][j][k] + (x[i + 1] - x[i]);
			dpcw[i + 1][j][k + (t[i + 1] >= tim)] = min(dpcw[i + 1][j][k + (t[i + 1] >= tim)], tim);
			tim = dpcw[i][j][k] + (x[i] + l - x[n - j]);
			dpccw[i][j + 1][k + (t[n - j] >= tim)] = min(dpccw[i][j + 1][k + (t[n - j] >= tim)], tim);
		}
		if(dpccw[i][j][k] < inf){
			tim = dpccw[i][j][k] + (x[n - j + 1] - x[n - j]);
			dpccw[i][j + 1][k + (t[n - j] >= tim)] = min(dpccw[i][j + 1][k + (t[n - j] >= tim)], tim);
			tim = dpccw[i][j][k] + (l - x[n - j + 1] + x[i + 1]);
			dpcw[i + 1][j][k + (t[i + 1] >= tim)] = min(dpcw[i + 1][j][k + (t[i + 1] >= tim)], 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(dpcw[i][j][k], dpccw[i][j][k]) < inf)
			ans = max(ans, k);
	}

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

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%d", &n, &l);
  ~~~~~^~~~~~~~~~~~~~~~
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", &x[i]);
                               ~~~~~^~~~~~~~~~~~~
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("%d", &t[i]);
                               ~~~~~^~~~~~~~~~~~~

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