Submission #231771

#	Time	Username	Problem	Language	Result	Execution time	Memory
231771		Haunted_Cpp	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	219 ms	135524 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];

int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, tamanho, mx = 0;
  cin >> n >> tamanho;
  n += 2;
  pos[0] = pos[n - 1] = 0;
  lim[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 (dp[L][R][Q][0] < 1e15 || dp[L][R][Q][1] < 1e15) mx = max (mx, Q);
        if (L + 1 < n && L + 1 < R) {
          // ESQ -> ESQ
          long long tempo = dp[L][R][Q][0] + pos[L + 1] - pos[L];
          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];
          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]);
          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];
          QTS = Q + (tempo <= lim[R - 1]);
          dp[L][R - 1][QTS][1] = min (dp[L][R - 1][QTS][1], tempo);       
        }  
      }
    }
  } 
  cout << mx << '\n';
  return 0;
}

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