제출 #38196

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38196		funcsr	구경하기 (JOI13_watching)	C++14	100 / 100	266 ms	17680 KiB

watching

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define index(a, b, y) (int)(lower_bound(a, b, y) - a)
#define INF 1000001919
inline void chmin(int &x, int v) { if (x > v) x = v; }
int N, A, B;
int X[2000];
int Fsmall[2000], Flarge[2000];
int dp[2001][2001];

bool f(int W) {
  rep(i, N) {
    Fsmall[i] = index(X, X+N, X[i]+W);
    Flarge[i] = index(X, X+N, X[i]+2*W);
  }
  rep(i, N+1) rep(j, A+1) dp[i][j] = INF;
  dp[0][0] = 0;
  rep(i, N) {
    rep(j, A+1) {
      if (dp[i][j] == INF) continue;
      if (j < A) chmin(dp[Fsmall[i]][j+1], dp[i][j]);
      if (dp[i][j] < B) chmin(dp[Flarge[i]][j], dp[i][j]+1);
    }
  }
  int m = INF;
  rep(i, A+1) chmin(m, dp[N][i]);
  return m <= B;
}

int main() {
  cin >> N >> A >> B;
  rep(i, N) cin >> X[i];
  sort(X, X+N);
  if (A+B >= N) {
    cout << 1 << "\n";
    return 0;
  }

  int lo = 0, hi = INF;
  while (hi-lo > 1) {
    int mid = (lo+hi)/2;
    if (f(mid)) hi = mid;
    else lo = mid;
  }
  cout << hi << "\n";
  return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50