Submission #747463

#	Time	Username	Problem	Language	Result	Execution time	Memory
747463		tch1cherin	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	979 ms	448796 KiB

ho_t3

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

const int INF = 1e9 + 1;

void chmin(int& a, int b) {
  a = min(a, b);
}

void solve() {
  int N, P;
  cin >> N >> P;
  vector<int> X(N), T(N);
  for (int &v : X) {
    cin >> v;
  }
  for (int &v : T) {
    cin >> v;
  }
  X.insert(X.begin(), 0);
  T.insert(T.begin(), 0);
  N++;
  vector dp(N, vector(N, vector(N, vector(2, INF))));
  dp[0][0][0][0] = 0;
  for (int len = 0; len < N - 1; len++) {
    for (int L = 0; L < N; L++) {
      int R = (L + len) % N;
      for (int ans = 0; ans < N; ans++) {
        for (int w = 0; w < 2; w++) {
          int time = dp[L][R][ans][w];
          if (w == 0) {
            {
              int delta = (X[L] - X[(L + N - 1) % N] + P) % P;
              int add = time + delta <= T[(L + N - 1) % N];
              chmin(dp[(L + N - 1) % N][R][ans + add][0], time + delta); 
            }
            {
              int delta = (X[(R + 1) % N] - X[L] + P) % P;
              int add = time + delta <= T[(R + 1) % N];
              chmin(dp[L][(R + 1) % N][ans + add][1], time + delta);
            }
          } else {
            {
              int delta = (X[R] - X[(L + N - 1) % N] + P) % P;
              int add = time + delta <= T[(L + N - 1) % N];
              chmin(dp[(L + N - 1) % N][R][ans + add][0], time + delta);
            }
            {
              int delta = (X[(R + 1) % N] - X[R] + P) % P;
              int add = time + delta <= T[(R + 1) % N];
              chmin(dp[L][(R + 1) % N][ans + add][1], time + delta);
            }
          }
        }
      }
    } 
  }
  int res = 0;
  for (int L = 0; L < N; L++) {
    for (int R = 0; R < N; R++) {
      for (int ans = 0; ans < N; ans++) {
        for (int w = 0; w < 2; w++) {
          if (dp[L][R][ans][w] != INF) {
            res = max(res, ans);
          }
        }
      } 
    }
  }
  cout << res << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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