Submission #1098551

#TimeUsernameProblemLanguageResultExecution timeMemory
1098551NurislamWatching (JOI13_watching)C++17
100 / 100
360 ms8204 KiB
#include <bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds;z #define pb push_back #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define int long long //#define ordst tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag , tree_order_statistics_node_update > //#define double long double template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int N = (1<<18) +1, inf = 1e18+200; //int mod = 998244353; //int mod = 1000000007; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng) void solve(){ int n, p, q; cin >> n >> p >> q; vector<int> a(n); for(int &i:a)cin >> i; if(p+q >= n){ cout << 1 << '\n'; return; } a.pb(0);a.pb(inf); sort(all(a)); //for(int &i:a)cout << i << ' '; //cout << '\n'; auto ok = [&](int m)->bool{ vector<vector<int>> dp(p+1, vector<int> (q+1)); dp[0][0] = 0; for(int x = 0; x <= p; x++){ for(int y = 0; y <= q; y++){ int cur = dp[x][y] + 1; if(cur > n)return true; //small //cout << x << ' ' << y << ' ' << cur << '\n'; if(x < p){ int l = lower_bound(all(a), a[cur] + m) - a.begin(); if(a[l] >= a[cur] + m)l--; chmax(dp[x+1][y], l); //cout << l << ' ' << a[cur] + m << " x+1 \n"; } if(y < q){ int l = lower_bound(all(a), a[cur] + m*2) - a.begin(); if(a[l] >= a[cur] + m*2)l--; chmax(dp[x][y+1], l); //cout << l << ' ' << a[cur]+2*m << " y+1 \n"; } } } return false; }; //bool s = ok(4); //cout << s << '\n'; int l = 1, r = a[n]-a[1], ans = 1; while(l <= r){ int m = (l+r)>>1; //cout << m << ' ' << ok(m) << '\n'; if(ok(m)){ ans = m; r = m-1; }else l = m+1; } cout << ans << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; //cin >> tt; while(tt--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...