Submission #1047374

#TimeUsernameProblemLanguageResultExecution timeMemory
1047374MinbaevWatching (JOI13_watching)C++17
100 / 100
642 ms7768 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second #define int long long #define ll long long #define pii pair<int,int> #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; void solve(){ cin >> n >> m >> k; vector<int>v(n+1); for(int i = 1;i<=n;i++)cin >> v[i]; sort(all(v)); if(m+k >= n){ cout << 1 << "\n"; return; } //~ for(auto to:v)cout << to << " "; //~ cout << "\n"; int l = 2, r = 1e9, ans = -1; while(l <= r){ int mid = (l+r)/2; bool flag = false; int dp[m+1][k+1]{}; for(int i = 0;i<=m;i++){ for(int j = 0;j<=k;j++){ if(i >= 1){ int h = v[dp[i-1][j] + 1] + mid - 1; int u = upper_bound(all(v), h) - v.begin() - 1; umax(dp[i][j], u); } if(j >= 1){ int h = v[dp[i][j-1] + 1] + 2*mid - 1; int u = upper_bound(all(v), h) - v.begin() - 1; umax(dp[i][j], u); } if(dp[i][j] == n)flag = true; } } if(flag){ r = mid - 1; ans = mid; } else l = mid + 1; } cout << ans << "\n"; } /* */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); //~ ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...