제출 #895526

#제출 시각아이디문제언어결과실행 시간메모리
895526nbphong구경하기 (JOI13_watching)C++14
100 / 100
163 ms17280 KiB
#include <bits/stdc++.h> // define ctdl #define ii pair<int,int> #define fi first #define se second #define ll long long // define files #define TASKS "EVENTS." #define fast ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; #define endl '\n' #define all(x) x.begin(),x.end() #define FORU(i,a,b) for(int i = a, _b = b; i <= _b ; i++) #define FORD(i,a,b) for(int i = a, _b = b; i >= _b ; i--) using namespace std; const int maxsub1 = 200, maxn = 2000,oo = 1e9 ; int n, numP, numQ ; int a[maxn+1] ; void getMin(int &x, int y) { x = min(x,y) ; } namespace sub1 { int dp[maxn+1][maxn+1]; bool check(int num) { memset(dp,0x3f,sizeof(dp)) ; dp[0][0] = 0 ; FORU(i,0,n) FORU(j,0,numP) if(dp[i][j] <= numQ) { int L = i + 1, R = i + 1 ; while(R <= n && a[L] + num-1 >= a[R] && j < numP) { getMin(dp[R][j+1],dp[i][j]) ; R++ ; } R = i + 1 ; while(R <= n && a[L] + num*2-1 >= a[R]) { getMin(dp[R][j],dp[i][j] + 1) ; R++ ; } } FORU(j,0,numP) if(dp[n][j] <= numQ) { return true ; } return false ; } void solve() { int L = 1, R = 1e9,ans =0 ; while(L <= R) { int mid = (L+R)>>1 ; if(check(mid)) R = mid - 1,ans=mid; else L = mid + 1 ; } cout << ans ; } } namespace lastsub { int dp[maxn+1][maxn+1] ; int p[maxn+1], q[maxn+1] ; bool check(int num) { memset(dp,0x3f,sizeof(dp)) ; dp[0][0] = 0 ; int tmp = 1 ; FORU(i,1,n) { while(tmp < n && a[i] + num - 1 >= a[tmp+1]) tmp++ ; p[i] = tmp ; } tmp = 1 ; FORU(i,1,n) { while(tmp < n && a[i] + num*2 - 1 >= a[tmp+1]) tmp++ ; q[i] = tmp ; } FORU(i,0,n) FORU(j,0,n) if(dp[i][j] <= numQ) { int R = p[i+1] ; getMin(dp[R][j+1],dp[i][j]) ; R = q[i+1] ; getMin(dp[R][j],dp[i][j] + 1) ; } FORU(j,0,numP) if(dp[n][j] <= numQ) return true ; return false ; } void solve() { int L = 1, R = 1e9,ans =0 ; while(L <= R) { int mid = (L+R)>>1 ; if(check(mid)) R = mid - 1,ans=mid; else L = mid + 1 ; } cout << ans ; } } int main() { fast ; //freopen(TASKS"INP","r",stdin) ; //freopen(TASKS"OUT","w",stdout) ; cin >> n >> numP >> numQ ; FORU(i,1,n) cin >> a[i] ; sort(&a[1],&a[n+1]) ; if(n <= numP + numQ) { cout << 1 ; return 0 ; } if(n <= 100) sub1::solve() ; else lastsub::solve() ; return 0 ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...