Submission #505845

#	Time	Username	Problem	Language	Result	Execution time	Memory
505845		cig32	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	201 ms	127436 KiB

ho_t3

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 3e5 + 10;
const int MOD = 1e9 + 7;
#define int long long

int rnd(int x, int y) { // random number generator
  int u= uniform_int_distribution<int>(x, y)(rng); return u;
}

void solve(int tc) {
  int N, L;
  cin >> N >> L;
  int x[N+2], t[N+1];
  x[0] = 0, x[N+1] = L;
  for(int i=1; i<=N; i++) {
    cin >> x[i];
  }
  for(int i=1; i<=N; i++) {
    cin >> t[i];
  }
  int dp[N+1][N+1][2][N+1]; 
  for(int i=0; i<=N; i++) {
    for(int j=0; j<=N; j++) {
      for(int k=0; k<2; k++) {
        for(int l=0; l<=N; l++) {
          dp[i][j][k][l] = 1e18;
        }
      }
    }
  }
  dp[0][0][0][0] = dp[0][0][1][0] = 0;
  for(int i=0; i<=N; i++) {
    for(int j=0; j<=N; j++) {
      if(i + j > N) continue;
      // k = 0
      for(int l=0; l<=N; l++) {
        // get
        if(l>0) {
          int hm = 1e18;
          if(i > 0) {
            hm = min(hm, dp[i-1][j][0][l-1] + x[i] - x[i-1]);
            hm = min(hm, dp[i-1][j][1][l-1] + L - x[N+1 - j] + x[i]);
          }
          if(i > 0 && hm <= t[i]) {
            dp[i][j][0][l] = min(dp[i][j][0][l], hm);
          }
          hm = 1e18;
          if(j > 0) {
            hm = min(hm, dp[i][j-1][0][l-1] + 2 * (x[i] + L - x[N+1 - j]));
            hm = min(hm, dp[i][j-1][1][l-1] + x[N+1 - (j-1)] - x[N+1 - j] + L - x[N+1 - j] + x[i]);
          }
          if(j > 0 && hm <= t[N+1 - j]) {
            dp[i][j][0][l] = min(dp[i][j][0][l], hm);
          }
        }
        // no get
        if(i>0) {
          dp[i][j][0][l] = min(dp[i][j][0][l], dp[i-1][j][0][l] + x[i] - x[i-1]);
          dp[i][j][0][l] = min(dp[i][j][0][l], dp[i-1][j][1][l] + L - x[N+1 - j] + x[i]);
        }
        if(j>0) {
          dp[i][j][0][l] = min(dp[i][j][0][l], dp[i][j-1][0][l] + 2 * (x[i] + L - x[N+1 - j]));
          dp[i][j][0][l] = min(dp[i][j][0][l], dp[i][j-1][1][l] + x[N+1 - (j-1)] - x[N+1 - j] + L - x[N+1 - j] + x[i]);
        }
      }
      //k = 1
      for(int l=0; l<=N; l++) {
        // get
        if(l>0) {
          int hm = 1e18;
          if(i > 0) {
            hm = min(hm, dp[i-1][j][0][l-1] + x[i] - x[i-1] + x[i] + L - x[N+1 - j]);
            hm = min(hm, dp[i-1][j][1][l-1] + 2 * (L - x[N+1 - j] + x[i]));
          }
          if(i > 0 && hm <= t[i]) {
            dp[i][j][1][l] = min(dp[i][j][1][l], hm);
          }
          hm = 1e18;
          if(j > 0) {
            hm = min(hm, dp[i][j-1][0][l-1] + x[i] + L - x[N+1 - j]);
            hm = min(hm, dp[i][j-1][1][l-1] + x[N+1 - (j-1)] - x[N+1 - j]);
          }
          if(j > 0 && hm <= t[N+1 - j]) {
            dp[i][j][1][l] = min(dp[i][j][1][l], hm);
          }
        }
        // no get
        if(i>0) {
          dp[i][j][1][l] = min(dp[i][j][1][l], dp[i-1][j][0][l] + x[i] - x[i-1] + x[i] + L - x[N+1 - j]);
          dp[i][j][1][l] = min(dp[i][j][1][l], dp[i-1][j][1][l] + 2 * (L - x[N+1 - j] + x[i]));
        }
        if(j>0) {
          dp[i][j][1][l] = min(dp[i][j][1][l], dp[i][j-1][0][l] + x[i] + L - x[N+1 - j]);
          dp[i][j][1][l] = min(dp[i][j][1][l], dp[i][j-1][1][l] + x[N+1 - (j-1)] - x[N+1 - j]);
        }
      }
    }
  }
  for(int i=N; i>=0; i--) {
    for(int j=0; j<=N; j++) {
      for(int k=0; k<=N; k++) {
        for(int l=0; l<2; l++) {
          if(dp[j][k][l][i] != 1e18) {
            cout << i << "\n";
            return;
          }
        }
      }
    }
  }
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

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