Submission #536146

#TimeUsernameProblemLanguageResultExecution timeMemory
536146michaoPinball (JOI14_pinball)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #define int long long #define mp make_pair #define pb push_back #define ld long double #define pii pair<int,int> #define sz(x) (int)x.size() #define piii pair<pii,pii> #define precise cout<<fixed<<setprecision(10) #define st first #define nd second #define ins insert #define vi vector<int> #define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) using namespace std; const int MAX=2005; const int inf=(int)1e9+9; int a[MAX]; int dp[MAX][MAX]; int r1[MAX]; int r2[MAX]; int n,p,q; bool check(int mid){ for (int i=0;i<=n;i++)for (int j=0;j<=n;j++)dp[i][j]=0; for (int i=1;i<=n;i++){ for (int j=1;j<=n;j++){ if (a[j]-a[i]+1<=mid)r1[i]=j; if (a[j]-a[i]+1<=mid*2)r2[i]=j; } } for (int i=0;i<=p;i++){ for (int j=0;j<=q;j++){ if (dp[i][j]==n)return true; int l=dp[i][j]+1; if (i!=p) dp[i+1][j]=max(dp[i+1][j],r1[l]); if (j!=q) dp[i][j+1]=max(dp[i][j+1],r2[l]); } } return false; } int32_t main(){ BOOST; cin>>n>>p>>q; p=min(p,n); q=min(q,n); for (int i=1;i<=n;i++)cin>>a[i]; sort(a+1,a+n+1); int ip=0,ik=inf; while (ip+1<ik){ int mid=(ip+ik)>>1; if (check(mid))ik=mid; else ip=mid; } cout<<ik; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...