Submission #203138

#TimeUsernameProblemLanguageResultExecution timeMemory
203138ZwariowanyMarcinCollecting Stamps 3 (JOI20_ho_t3)C++14
0 / 100
5 ms376 KiB
#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 (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);
               ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...