oj.uz

Submission #203138

# Submission time Handle Problem Language Result Execution time Memory
203138 2020-02-19T13:21:56 Z ZwariowanyMarcin Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 5 ms 376 KB 
#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 - lewo];
						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

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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Incorrect 5 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -