Submission #231770

#	Time	Username	Problem	Language	Result	Execution time	Memory
231770		Haunted_Cpp	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	231 ms	135416 KiB

ho_t3

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

#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

const int N = 2e2 + 5;

long long dp [N][N][N][2];

int pos [N];
int lim [N];
 
/*
 * DP[N][N][N][2]
 * Minimum time possible for being at pos [i, j] - 0 / 1, with x elements so far
 */ 

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, tamanho;
  cin >> n >> tamanho;
  n += 2;
  pos[0] = 0;
  lim[0] = 1e9;
  pos[n - 1] = 0;
  lim[n - 1] = 1e9;
  for (int i = 1; i < n - 1; i++) cin >> pos[i];
  for (int i = 1; i < n - 1; i++) cin >> lim[i];
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int x = 0; x < N; x++) {
        dp[i][j][x][0] = dp[i][j][x][1] = 1e16;
      }
    }
  }
  dp[0][n - 1][0][0] = dp[0][n - 1][0][1] = 0;
  

  for (int L = 0; L < n; L++) {
    for (int R = n - 1; R >= 0; R--) {
      for (int Q = 0; Q <= n; Q++) {
        
        if (L + 1 < n && L + 1 < R) {
          
          // ESQ -> ESQ
          long long tempo = dp[L][R][Q][0] + pos[L + 1] - pos[L];
          assert(tempo >= 0);
          int QTS = Q + (tempo <= lim[L + 1]);
      
          dp[L + 1][R][QTS][0] = min (dp[L + 1][R][QTS][0], tempo);
          
          
          // DIR -> ESQ
          tempo = dp[L][R][Q][1] + tamanho - pos[R] + pos[L + 1];
          assert(tempo >= 0);
          QTS = Q + (tempo <= lim[L + 1]);
          dp[L + 1][R][QTS][0] = min (dp[L + 1][R][QTS][0], tempo);
          
        }
        
        if (R - 1 >= 0 && R - 1 > L) {
          
          // DIR -> DIR
          long long tempo = dp[L][R][Q][1] + abs (pos[R] - pos[R - 1]);
          assert(tempo >= 0);
          int QTS = Q + (tempo <= lim[R - 1]);
          dp[L][R - 1][QTS][1] = min (dp[L][R - 1][QTS][1], tempo);
          
          
          // ESQ -> DIR
          
          tempo = dp[L][R][Q][0] + pos[L] + tamanho - pos[R - 1];
          assert(tempo >= 0);
          QTS = Q + (tempo <= lim[R - 1]);
          dp[L][R - 1][QTS][1] = min (dp[L][R - 1][QTS][1], tempo);
          
        }
        
      }
    }
  } 
  
  int mx = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      for (int x = 0; x < N; x++) {
        if (dp[i][j][x][0] < 1e15 || dp[i][j][x][1] < 1e15) {
     //     cout << i << ' ' << j << ' ' <<' ' << x << ' ' << dp[i][j][x][1] << '\n';
          mx = max (mx, x);
        }
      }
    }
  }
  cout << mx << '\n';
  return 0;
}

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