Submission #651614

#TimeUsernameProblemLanguageResultExecution timeMemory
651614Koful123Watching (JOI13_watching)C++17
50 / 100
170 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define endl "\n" #define pb push_back #define ff first #define ss second #define mod 1000000007 #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() int n,p,q; vector<int> v; vector<vector<vector<pair<bool,bool>>>> dp; bool f(int pos,int p,int q,int w){ if(p < 0 || q < 0) return false; if(pos >= n) return true; if(dp[pos][p][q].ss) return dp[pos][p][q].ff; int a = lower_bound(all(v),v[pos] + w) - v.begin(); int b = lower_bound(all(v),v[pos] + 2*w) - v.begin(); dp[pos][p][q].ff = ((a > pos && f(a,p-1,q,w)) || (b > pos && f(b,p,q-1,w))); dp[pos][p][q].ss = true; return dp[pos][p][q].ff; } bool check(int m){ for(int i=0;i<n;i++){ for(int j=0;j<=p;j++){ for(int k=0;k<=q;k++){ dp[i][j][k].ff = dp[i][j][k].ss = false; } } } return f(0,p,q,m); } void solve(){ cin >> n >> p >> q; v.assign(n,0); for(int i=0;i<n;i++){ cin >> v[i]; } if(p + q >= n){ cout << 1 << endl; return; } dp.assign(n,vector<vector<pair<bool,bool>>>(p+1,vector<pair<bool,bool>>(q+1,{false,false}))); sort(all(v)); int l = 1,r = 1e9; while(l < r){ int m = (l + r) / 2; if(check(m)) r = m; else l = m + 1; } cout << l << endl; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while(t--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...