Submission #230968

#	Time	Username	Problem	Language	Result	Execution time	Memory
230968		AlexLuchianov	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	1087 ms	978700 KiB

ho_t3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200;
ll const inf = 2000000000;

ll v[5 + nmax], t[5 + nmax];
ll dp[5 + 2 * nmax][5 + 2 * nmax][5 + nmax][2];

int n;

ll extract(int x, int y, int val, int h){
  if(val < 0)
    return inf;
  else
    return dp[x][y][val][h];
}

ll dist(int x, int y){
  return fabs(v[x] - v[y]);
}

void update(ll &number, ll val){
  number = min(number, val);
}

int main()
{
  int l;
  cin >> n >> l;
  for(int i = 1;i <= n; i++)
    cin >> v[i];
  for(int i = 1;i <= n; i++)
    cin >> t[i];
  for(int i = 1;i <= n; i++) {
    v[n + i] = v[i] + l;
    t[n + i] = t[i];
  }

  for(int i = 0;i <= nmax * 2; i++)
    for(int j = 0; j <= nmax * 2; j++)
      for(int h = 0; h <= nmax; h++)
        dp[i][j][h][0] = dp[i][j][h][1] = inf;

  dp[n][n][(abs(l - v[n]) <= t[n])][0] = fabs(l - v[n]);
  dp[n + 1][n + 1][(abs(l - v[n + 1]) <= t[n + 1])][0] = fabs(l - v[n + 1]);

  int result = 0;

  for(int dif = 0; dif < n; dif++)
    for(int i = 1;i <= 2 * n; i++){
      int j = i + dif;
      if(j <= 2 * n){
        for(int k = 0; k <= dif + 1; k++){

          ll time = dp[i][j][k][0] + dist(i - 1, i);
          update(dp[i - 1][j][k + (time <= t[i - 1])][0], time);

          time = dp[i][j][k][1] + dist(i - 1, j);
          update(dp[i - 1][j][k + (time <= t[i - 1])][0], time);

          time = dp[i][j][k][0] + dist(j + 1, i);
          update(dp[i][j + 1][k + (time <= t[j + 1])][1], time);

          time = dp[i][j][k][1] + dist(j + 1, j);
          update(dp[i][j + 1][k + (time <= t[j + 1])][1], time);

          if(dp[i][j][k][0] <= inf - 5 || dp[i][j][k][1] <= inf - 5)
            result = max(result, k);

        }
      }
    }
  cout << result;
  return 0;
}

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