Submission #202884

#	Time	Username	Problem	Language	Result	Execution time	Memory
202884		EntityIT	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	137 ms	65532 KiB

ho_t3

#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

template<class T>
inline bool asMn(T &a, const T &b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T &a, const T &b) { return a < b ? a = b, true : false; }

inline int nxt(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int prv(int i, int n) { return !i ? n - 1 : i - 1; }

const int inf = 1e9 + 100;
mt19937 rng( (uint32_t)chrono::steady_clock::now().time_since_epoch().count() );

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  #ifdef FourLeafClover
  freopen("input", "r", stdin);
  #endif // FourLeafCLover

  int n, l; cin >> n >> l;
  vector<int> x(n), t(n);
  for (auto &i : x) cin >> i;
  for (auto &i : t) cin >> i;

  vector<vector<vector<array<int, 2> > > > f(n + 1, vector<vector<array<int, 2> > >(n + 1, vector<array<int, 2> >(n + 1, array<int, 2>{ inf, inf } ) ) );
  f[0][n][n][0] = 0;

  for (int nStamp = 0; nStamp < n; ++nStamp) {
    for (int i = n; ~i; --i) {
      for (int j = n, cnt = 0; (j == n && !cnt) || j < i; j = nxt(j, n + 1), cnt += (j == n) ) {
        for (int side = 0; side < 2; ++side) if (f[nStamp][i][j][side] < inf) {
          int prvI = prv(i, n + 1), nxtJ = nxt(j, n + 1);
          if (!side) {
            if (prvI != j) asMn(f[nStamp + (f[nStamp][i][j][side] + (i == n ? l : x[i]) - x[prvI] <= t[prvI])][prvI][j][0],
                                f[nStamp][i][j][side] + (i == n ? l : x[i]) - x[prvI]);
            if (nxtJ != i) asMn(f[nStamp + (f[nStamp][i][j][side] + (i == n ? 0 : l - x[i]) + x[nxtJ] <= t[nxtJ])][i][nxtJ][1],
                                f[nStamp][i][j][side] + (i == n ? 0 : l - x[i]) + x[nxtJ]);
          }
          else {
            if (prvI != j) asMn(f[nStamp + (f[nStamp][i][j][side] + (j == n ? 0 : x[j]) + l - x[prvI] <= t[prvI])][prvI][j][0],
                                f[nStamp][i][j][side] + (j == n ? 0 : x[j]) + l - x[prvI]);
            if (nxtJ != i) asMn(f[nStamp + (f[nStamp][i][j][side] + x[nxtJ] - (j == n ? 0 : x[j]) <= t[nxtJ])][i][nxtJ][1],
                                f[nStamp][i][j][side] + x[nxtJ] - (j == n ? 0 : x[j]));
          }
        }
      }
    }
  }

  int ans = 0;
  for (int nStamp = 1; nStamp <= n; ++nStamp) {
    for (int i = n; ~i; --i) {
      for (int j = n, cnt = 0; (j == n && !cnt) || j < i; j = nxt(j, n + 1), cnt += (j == n) ) {
        for (int side = 0; side < 2; ++side) if (f[nStamp][i][j][side] < inf) ans = nStamp;
      }
    }
  }

  cout << ans << '\n';

  return 0;
}

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