제출 #564937

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

watching

#include <bits/stdc++.h>
using namespace std;
int main(){
  int N, P, Q;
  cin >> N >> P >> Q;
  P = min(P, N);
  Q = min(Q, N);
  vector<int> A(N);
  for (int i = 0; i < N; i++){
    cin >> A[i];
  }
  sort(A.begin(), A.end());
  int tv = 500000000, fv = 0;
  while (tv - fv > 1){
    int mid = (tv + fv) / 2;
    vector<int> R1(N), R2(N);
    for (int i = 0; i < N; i++){
      R1[i] = lower_bound(A.begin(), A.end(), A[i] + mid) - A.begin();
      R2[i] = lower_bound(A.begin(), A.end(), A[i] + mid * 2) - A.begin();
    }
    vector<vector<vector<bool>>> dp(N + 1, vector<vector<bool>>(P + 1, vector<bool>(Q + 1, false)));
    dp[0][0][0] = true;
    for (int i = 0; i < N; i++){
      for (int j = 0; j <= P; j++){
        for (int k = 0; k <= Q; k++){
          if (dp[i][j][k]){
            if (j < P){
              dp[R1[i]][j + 1][k] = true;
            }
            if (k < Q){
              dp[R2[i]][j][k + 1] = true;
            }
          }
        }
      }
    }
    bool ok = false;
    for (int i = 0; i <= P; i++){
      for (int j = 0; j <= Q; j++){
        if (dp[N][i][j]){
          ok = true;
        }
      }
    }
    if (ok){
      tv = mid;
    } else {
      fv = mid;
    }
  }
  cout << tv << endl;
}

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