COLOCON -Colopl programming contest 2018 D - すぬけそだて――トレーニング――

問題ページ D - すぬけそだて――トレーニング――

このブログは解説ではなくクソポエムです

感想

解説を実装しただけ
実装に無駄に時間をかけてしまったので反省
lower_boundとかupper_boundでいまだに混乱するのをやめたい

monge性とかスライド最小値、セグ木でDPの遷移を高速化するやつはまだいらないテクかなーと思って放置していたけど強い人がアルゴリズムで殴るのに使っていたしそろそろ覚えたい。勉強して通したら追記する。

#define __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

// dp[i][j] = (T[i]が最後に起動した時刻でそれまでにj回起動している)
// t[i]から遷移する先は2パターンしかない
int dp[5010][5010], t[5010], nxt[5010];
signed main(void)
{
  int n, x;
  cin >> n >> x;
  REP(i, n) cin >> t[i];

  REP(i, n) {
    // t[i] + X >= t[j] となる最大のjを求めておく
    int lb = 0, ub = n;
    while(ub - lb > 1) {
      int mid = (ub+lb)/2;
      if(t[i] + x >= t[mid]) lb = mid;
      else ub = mid;
    }
    nxt[i] = lb;
  }

  dp[0][0] = x;
  REP(i, n) REP(j, n) {
    // dp[i][j] からは dp[nxt[i]][j+1] と dp[nxt[i]+1][j+1] に遷移
    chmax(dp[nxt[i]][j+1], dp[i][j] + min(t[nxt[i]] - t[i], x));
    chmax(dp[nxt[i]+1][j+1], dp[i][j] + min(t[nxt[i]+1] - t[i], x));
  }

  REP(i, n) {
    int ret = 0;
    REP(j, n) {
      chmax(ret, dp[j][i]);
    }
    cout << ret << endl;
  }

  return 0;
}