제출 #795221

#제출 시각아이디문제언어결과실행 시간메모리
795221raysh07구경하기 (JOI13_watching)C++17
100 / 100
541 ms30364 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 #define f first #define s second mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); void Solve() { int n, p, q; cin >> n >> p >> q; vector <int> a(n); for (auto &x : a) cin >> x; sort(a.begin(), a.end()); int l = 1, r = 1e9; if (p + q > n){ cout << 1 << "\n"; return; } while (r != l){ int mid = (l + r)/2; vector<vector<int>> dp(n + 1, vector<int>(p + 1, INF)); dp[0][0] = 0; for (int i = 1; i <= n; i++){ int idx = lower_bound(a.begin(), a.end(), a[i - 1] + mid) - a.begin(); int idx1 = lower_bound(a.begin(), a.end(), a[i - 1] + 2 * mid) - a.begin(); for (int j = 0; j <= p; j++){ if (j != p) dp[idx][j + 1] = min(dp[idx][j + 1], dp[i - 1][j]); dp[idx1][j] = min(dp[idx1][j], dp[i - 1][j] + 1); } } bool good = false; for (int j = 0; j <= p; j++){ if (dp[n][j] <= q) good = true; } if (good) r = mid; else l = mid + 1; } cout << l << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...