Submission #1256115

#TimeUsernameProblemLanguageResultExecution timeMemory
1256115rajinnyoWatching (JOI13_watching)C++20
100 / 100
101 ms16396 KiB
#include<bits/stdc++.h> using namespace std; // JANGAN LUPA CEK PERLU LL NGGAK #define pb push_back #define pii pair<int,int> #define fi first #define inf INT_MAX #define se second #define miku ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); vector<int>a; signed main(){ miku int n,p,q;cin>>n>>p>>q; q=min(n,q); a.assign(n+1,0); for(int i=1;i<=n;i++)cin>>a[i]; sort(a.begin()+1,a.end()); int l=1,r=a[n]-a[1]+1; int ans=0; while(l<=r){ int mid=(l+r)/2; int j=1; int mini=inf; int dp[n+10][q+10]; memset(dp,0,sizeof(dp)); int deketk=1,deket2k=1; for(int i=1;i<=n;i++){ while(a[i]-a[deketk]+1>mid)deketk++; while(a[i]-a[deket2k]+1>2*mid)deket2k++; dp[i][0]=dp[deketk-1][0]+1; for(int j=1;j<=q;j++){ dp[i][j]=dp[deket2k-1][j-1]; dp[i][j]=min(dp[deketk-1][j]+1,dp[i][j]); // if(mid==2) cout<<i<<" "<<j<<" "<<dp[binser(i,2*mid)-1][j-1]<<" "<<dp[binser(i,2*mid)-1][j-1]<<endl; } } for(int i=0;i<=q;i++) mini=min(mini,dp[n][i]); // cout<<mid<<' '<<mini<<endl; if(mini<=p){ r=mid-1; ans=mid; } else l=mid+1; } cout<<ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...