Submission #743416

#TimeUsernameProblemLanguageResultExecution timeMemory
743416Valters07Watching (JOI13_watching)C++14
100 / 100
526 ms15952 KiB
#include <bits/stdc++.h> #define fio ios_base::sync_with_stdio(0);cin.tie(0); #define en cin.close();return 0; #define ll long long #define pb push_back #define fi first #define se second using namespace std; const int N = 2e3+5; int dp[N][N];// pos, c0 taken = min c1 taken bool check(vector<int> &pos, int c0, int c1, int w) { int n = pos.size()-1; int k1 = 1, k2 = 2; if(c0>c1) swap(c0,c1), swap(k1,k2); for(int j = 0;j<=c0;j++) { int it0 = 1, it1 = 1; for(int i = 1;i<=n;i++) { while(pos[i]-pos[it0]+1>w*k1) it0++; while(pos[i]-pos[it1]+1>w*k2) it1++; dp[i][j]=dp[it1-1][j]+1; if(j>0) dp[i][j]=min(dp[i][j],dp[it0-1][j-1]); } } int minc1 = 1e9; for(int i = 0;i<=c0;i++) minc1=min(minc1,dp[n][i]); return (minc1<=c1); } int main() { // ifstream cin("in.in"); int n, c0, c1; cin >> n >> c0 >> c1; if(n<=c0+c1) return cout << 1, 0; vector<int> pos(n+1); for(int i = 1;i<=n;i++) cin >> pos[i]; sort(pos.begin()+1,pos.end()); for(int i = 1;i<=n;i++) dp[0][i]=n; int l = 1, r = 1e9; while(l<r) { int mid = (l+r)/2; if(check(pos,c0,c1,mid)) r=mid; else l=mid+1; } cout << l; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...