Submission #264753

#TimeUsernameProblemLanguageResultExecution timeMemory
264753AtalasionWatching (JOI13_watching)C++14
100 / 100
207 ms32124 KiB
//khodaya khodet komak kon #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define all(x) x.begin(), x.end() #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") #define int long long using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; const int N = 2000 + 10; const ll MOD = 1000000000 + 7; const ll INF = 1000000000000000010; const ll LOG = 25; int dp[N][N], n, p, q, a[N], nxt[N], nxt2[N]; bool isval(int w){ //cout << w << ' '; memset(dp, 0, sizeof dp); memset(nxt, 0, sizeof nxt); memset(nxt2, 0, sizeof nxt2); int pnt = 1, pnt2 = 1; for (int i = 1; i <= n - 1; i++){ while (a[pnt + 1] - a[i] <= w - 1) pnt++; while (a[pnt2 + 1] - a[i] <= 2 * w - 1) pnt2++; nxt[i] = pnt; nxt2[i] = pnt2; } for (int i = 0; i <= p; i++) for (int j = 0; j <= q; j++){ int x = dp[i][j]; //cout << i << ' ' << j << ' ' << dp[i][j] << '\n'; x++; if (dp[i][j] >= n - 1) return 1; dp[i + 1][j] = max(dp[i + 1][j], nxt[x]); dp[i][j + 1] = max(dp[i][j + 1], nxt2[x]); } // cout << dp[p][q] << '\n'; return (dp[p][q] >= n - 1); } int32_t main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> p >> q; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); n++; a[n] = INF; int l = 0, r = 1000000000; while (r - l > 1){ int md = (l + r) >> 1; if (isval(md)) r = md; else l = md; } cout << r; // isval(32); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...