제출 #1252727

#제출 시각아이디문제언어결과실행 시간메모리
1252727ilhan_arda구경하기 (JOI13_watching)C++20
100 / 100
82 ms15940 KiB
//~ #pragma GCC optimize("O3,unroll-loops") //~ #pragma GCC target("avx,avx2,fma") #include <bits/stdc++.h> #define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define fi first #define se second #define pb push_back #define endl "\n" //~ #define int long long using namespace std; typedef long long ll; typedef pair<int, int> ii; typedef tuple<int, int, int> iii; const int inf = INT_MAX; const int mod = 1e9+7; int n, p, q; int a[2005], dp[2005][2005]; bool check(int w){ for(int i=n;i>=1;i--){ int ind1 = upper_bound(a+1, a+n+1, a[i]+w-1) - a; int ind2 = upper_bound(a+1, a+n+1, a[i]+2*w-1) - a; for(int j=0;j<=p;j++){ int t1 = inf, t2 = inf; if(j)t1 = dp[ind1][j-1]; t2 = dp[ind2][j]+1; dp[i][j] = min(t1, t2); } } if(dp[1][p]<=q)return true; else return false; } int32_t main(){ fast; cin>>n>>p>>q; for(int i=1;i<=n;i++){ cin>>a[i]; } sort(a+1, a+n+1); if(p + q >= n){ cout<<1<<endl; return 0; } int l = 1, r = 1e9; while(l<=r){ int m = (l+r)/2; if(check(m)){ r = m-1; } else l = m+1; } cout<<l<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...