Submission #203139

#	Time	Username	Problem	Language	Result	Execution time	Memory
203139		ZwariowanyMarcin	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	185 ms	134716 KiB

ho_t3

#include <bits/stdc++.h>
#define LL long long
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)

using namespace std;

const int nax = 211;

void mini(LL &a, LL b) {
	if (a == -1) 
		a = b;
	else
		a = min(a, b);
}

int n, L;
int x[nax];
int T[nax];
int best;

LL dp[nax][nax][nax][2];


int main() {
	scanf ("%d%d", &n, &L);
	rep(i, 1, n) scanf ("%d", x + i);
	rep(i, 1, n) scanf ("%d", T + i);
	
	rep(i, 0, n) rep(j, 0, n) rep(k, 0, n) rep(g, 0, 1) dp[i][j][k][g] = -1;
	dp[0][0][0][0] = 0;
	
	rep(wynik, 0, n)
		rep(l, 0, n)
			rep(r, 0, n) 
				rep(g, 0, 1) {
					if (dp[wynik][l][r][g] == -1) continue;
					best = max(best, wynik);
					if (l == 0 && r == 0) {
						int nw = ((L - x[n]) <= T[n]);
						dp[nw][1][0][0] = L - x[n];
						nw = (x[1] <= T[1]);
						dp[nw][0][1][1] = x[1];
						continue;
					}
					if (l + r >= n) continue;
					LL lewo = x[n - l + 1] - x[n - l];
					LL prawo = x[r + 1] - x[r];
					LL czas = dp[wynik][l][r][g];
					assert(0 <= czas);
					if (g == 0) {
						assert(0 < lewo);
						int nw = wynik + (czas + lewo <= T[n - l]);
						mini(dp[nw][l + 1][r][0], czas + lewo);
						LL droga = L - x[n - l + 1] + x[r + 1];
						assert(0 < droga);
						nw = wynik + (czas + droga <= T[r + 1]);
						mini(dp[nw][l][r + 1][1], czas + droga);
					}
					if (g == 1) {
						assert(0 < prawo);
						int nw = wynik + (czas + prawo <= T[r + 1]);
						mini(dp[nw][l][r + 1][1], czas + prawo);
						LL droga = x[r] + L - x[n - l];
						assert(0 < droga);
						nw = wynik + (czas + droga <= T[n - l]);
						mini(dp[nw][l + 1][r][0], czas + droga);
					}
				}
	printf ("%d\n", best);
						
						
						
				
	
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:32:8: 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:33:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf ("%d", x + i);
               ~~~~~~^~~~~~~~~~~~~
ho_t3.cpp:34:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  rep(i, 1, n) scanf ("%d", T + i);
               ~~~~~~^~~~~~~~~~~~~

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