SRM451 Div1 Medium

500

dp[どれを最後に拾った][最後に足したK] = 最大
i 番目の次に j 番目を拾おうとする場合、最小でも、
k + (k + 1) + (k + 2) + ... (k + (j - k)) = (j - k) * k + ((k + 1) * k / 2)
だけは足す必要がある。それ以上であれば、移動可能ということになる。
あとはいつもどおり DP する。

const int N = 50 + 1;
const int M = 100000 + 1;
int dp[N][M];

class BaronsAndCoins {
public:
  int getMaximum(vector <int> x, vector <int> y)
  {
    x.push_back(0);
    y.push_back(0);
    const int n = x.size();
    {
      vector< pair<int, int> > ord;
      for (int i = 0; i < n; ++i) {
        ord.push_back(make_pair(y[i], x[i]));
      }
      sort(ord.begin(), ord.end());
      for (int i = 0; i < n; ++i) {
        y[i] = ord[i].first;
        x[i] = ord[i].second;
      }
    }

    fill(&dp[0][0], &dp[N - 1][M - 1] + 1, -(1 << 28));
    dp[0][0] = 0;
    for (int curr = 0; curr < n; ++curr) {
      for (int k = 0; k < M; ++k) {
        if (dp[curr][k] < 0) continue;
        for (int next = curr + 1; next < n; ++next) {
          unless (y[curr] < y[next]) continue;
          int turn = y[next] - y[curr];
          int mn = (k * turn) + (turn * (turn + 1)) / 2;
          if (x[curr] + mn <= x[next]) {
            int m = x[next] - (x[curr] + mn);
            int small = (m / turn) + (bool)(m % turn);
            int next_k = k + small + turn;
            if (next_k < M) {
              dp[next][next_k] = max(dp[next][next_k], dp[curr][k] + 1);
            }
          }
        }
      }
    }
    return *max_element(&dp[0][0], &dp[N - 1][M - 1] + 1);
  }
};