Submission #1002042

#TimeUsernameProblemLanguageResultExecution timeMemory
1002042HasanV11010238Watching (JOI13_watching)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define INF 1000000000 int n, p, q; vector<int> a; int main(){ cin>>n>>p>>q; a.assign(n + 1, 0); for (int i = 1; i <= n; i++){ cin>>a[i]; } sort(a.begin(), a.end()); if (n <= p + q){ cout<<1; return 0; } ll dp[n + 1][p + q + 1]; int l = 1, r = 15, w = -1; while (l <= r){ int mid = (l + r) / 2; for (int i = 0; i <= n; i++){ for (int j = 0; j <= p + q; j++){ dp[i][j] = 0; } } for (int i = 1; i <= n; i++){ for (int j = 0; j <= p + q; j++){ if (i <= p + q){ dp[i][j] = 1; continue; } for (int k = i - 1; k >= 0; k--){ if (a[i] - a[k] + 1 > 2 * mid) break; if (a[i] - a[k] + 1 <= 2 * mid && j != 0) dp[i][j] = max(dp[i][j], dp[k][j - 1]); if (a[i] - a[k] + 1 <= mid) dp[i][j] = max(dp[i][j], dp[k][j]); } } } if (dp[n][q] == 1){ r = mid - 1; w = mid; } else{ l = mid + 1; } } cout<<w; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...