Submission #924074

#	Time	Username	Problem	Language	Result	Execution time	Memory
924074		rolandpetrean	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	36 ms	135260 KiB

ho_t3

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

using ll = long long;
#define int ll

#define endl '\n'
#define pb push_back
using pi = pair<int, int>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

const int N = 205, INF = 1e14;

int n, len;
int x[N], t[N];

// dp[l][r][k][0/1] - timpul minim daca iau prefix l, sufix r, k stampile si 0 (sunt pe prefix) sau 1 (sunt pe sufix)
int dp[N][N][N][2];
int solve(int l, int r, int k, int w) {
  if (dp[l][r][k][w] != -1) return dp[l][r][k][w];
  
  dp[l][r][k][w] = INF;
  
  if (w == 0) {
    //if (l == 0 && r == 1 && k == 0) cout << solve(0, 1, 0, 1) << "!\n";
    if (r != 0) ckmin(dp[l][r][k][0], solve(l, r, k, 1) + len - x[n - r + 1]);
    if (l > 0) {
      int dist = x[l] - x[l - 1];
      int same = solve(l - 1, r, k, 0);
      ckmin(dp[l][r][k][0], same + dist);
      
      if (k > 0) {
        int take = solve(l - 1, r, k - 1, 0);
        if (take + dist <= t[l]) ckmin(dp[l][r][k][0], take + dist);
      }
    }
  } else {
    if (l != 0) ckmin(dp[l][r][k][1], solve(l, r, k, 0) + x[l]);
    if (r > 0) {
      int dist = x[n - r + 2] - x[n - r + 1];
      int same = solve(l, r - 1, k, 1);
      ckmin(dp[l][r][k][1], same + dist);
      
      if (k > 0) {
        int take = solve(l, r - 1, k - 1, 1);
        if (take + dist <= t[n - r + 1]) ckmin(dp[l][r][k][1], take + dist);
      }
    }
  }
  
  // cout << l << " " << r << " " << k << " " << w << "! " << dp[l][r][k][w] << endl;
  
  return dp[l][r][k][w];
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  
  cin >> n >> len;
  
  for (int i = 1; i <= n; ++i) cin >> x[i];
  for (int i = 1; i <= n; ++i) cin >> t[i];
  x[0] = 0;
  x[n + 1] = len;
  
  memset(dp, -1, sizeof(dp));
  for (int w = 0; w <= 1; ++w) dp[0][0][0][w] = 0;
  
  int ans = 0;
  for (int k = 1; k <= n; ++k) {
    for (int l = 0; l <= n; ++l) {
      int r = n - l;
      for (int w = 0; w <= 1; ++w) {
        if (solve(l, r, k, w) != INF) ans = k;
      }
    }
  }
  
  cout << ans;
}

/*
5 20
4 5 8 13 17
18 23 15 7 10
*/

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