제출 #236828

#제출 시각아이디문제언어결과실행 시간메모리
236828apostoldaniel854구경하기 (JOI13_watching)C++14
100 / 100
276 ms16120 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" void _ (int &a, int b) { if (a > b) a = b; } const int N = 2000; int dp[1 + N][1 + N]; int a[1 + N]; int n, p, q; bool check (int w) { for (int i = 0; i <= n; i++) for (int j = 0; j <= p; j++) dp[i][j] = q + 1; dp[0][0] = 0; int x = 0, y = 0; for (int i = 1; i <= n; i++) { while (a[x] + w <= a[i]) x++; if (x) x--; while (a[y] + 2 * w <= a[i]) y++; if (y) y--; for (int j = 0; j <= p; j++) { if (j) _ (dp[i][j], dp[x][j - 1]); _ (dp[i][j], dp[y][j] + 1); } } for (int i = 0; i <= p; i++) if (dp[n][i] <= q) return true; return false; } int main () { cin >> n >> p >> q; _ (p, n); _ (q, n); for (int i = 1; i <= n; i++) cin >> a[i]; sort (a + 1, a + n + 1); int lb = 1, rb = (1 << 30); int bestW = 0; while (lb <= rb) { int mid = (lb + rb) / 2; if (check (mid)) bestW = mid, rb = mid - 1; else lb = mid + 1; } cout << bestW << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...