제출 #1125185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125185		fryingduc	Collecting Stamps 3 (JOI20_ho_t3)	C++20	15 / 100	97 ms	135288 KiB

ho_t3

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 205;
int n, l;
int x[maxn], t[maxn];
long long f[maxn][maxn][maxn][2];

void solve() {
  cin >> n >> l;
  for(int i = 1; i <= n; ++i) {
    cin >> x[i];
    x[i + n + 1] = x[i];
  }
  for(int i = 1; i <= n; ++i) {
    cin >> t[i];
    t[i + n + 1] = t[i];
  }
  x[n + 1] = l;
  memset(f, 0x3f, sizeof(f));
  f[0][n + 1][0][0] = f[0][n + 1][0][1] = 0;
  for(int i = 0; i <= n; ++i) {
    for(int j = n + 1; j > i; --j) {
      for(int score = 0; score <= (i + (n - j + 1)); ++score) {
        if(f[i][j][score][1] < 1e18) {
          if(j - 1 > i) {
            long long time = f[i][j][score][1] + (x[j] - x[j - 1]);
            int add = (time <= t[j - 1]);
            f[i][j - 1][score + add][1] = min(f[i][j - 1][score + add][1], time);
          }
          if(i + 1 < j) {
            long long time = f[i][j][score][1] + (l - x[j] + x[i + 1]);
            int add = (time <= t[i + 1]);
            f[i + 1][j][score + add][0] = min(f[i + 1][j][score + add][0], time);
          }
        }
        if(f[i][j][score][0] < 1e18) {
          if(j - 1 > i) {
            long long time = f[i][j][score][0] + (x[i] + l - x[j - 1]);
            int add = (time <= t[j - 1]);
            f[i][j - 1][score + add][1] = min(f[i][j - 1][score + add][1], time);
          }
          if(i + 1 < j) {
            long long time = f[i][j][score][0] + (x[i + 1] - x[i]);
            int add = (time <= t[i + 1]);
            f[i + 1][j][score + add][0] = min(f[i + 1][j][score + add][0], time);
          }
        }
//        debug(i, j, score, f[i][j][score][0], f[i][j][score][1]);
      }
    }
  }
  int res = 0;
  for(int i = 0; i <= n; ++i) {
    for(int j = n + 1; j > i; --j) {
      for(int score = 0; score <= n; ++score) {
        for(int at = 0; at < 2; ++at) {
          if(f[i][j][score][at] < 1e18) {
            if(res < score) {
              res = score;
              debug(i, j, score, at, f[i][j][score][at]);
            }
          }
        }
      }
    }
  }
  cout << res;
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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