Submission #498301

#TimeUsernameProblemLanguageResultExecution timeMemory
498301s_samchenkoSwimming competition (LMIO18_plaukimo_varzybos)C++17
100 / 100
415 ms22712 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> //#pragma GCC optimize("Ofast") //#pragma GCC target ("avx2") #define ll long long #define ff first #define ss second #define int ll #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define pii pair <int, int> #define pdd pair <double, double> #define vi vector <int> using namespace std; using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; const int inf = 1e15; const int mod = 1e9+7; const int N = 2e5+100; int n, a, b; vector <int> v; bool check(int k){ vector <int> dp(n+100); dp[0] = 1; for (int i = 0, j = 1; i < n; ++i){ if (i > 1) dp[i] += dp[i-1]; if (dp[i] <= 0) continue; j = max(j, i + 1); while (j < n && v[j] - v[i] <= k) ++j; if (i + a <= min(i + b, j)) { dp[i+a]++; dp[min(i + b, j) + 1]--; } } dp[n] += dp[n-1]; return dp[n] > 0; } void solve(){ cin >> n >> a >> b; v.resize(n); for (int i = 0; i < n; ++i) cin >> v[i]; sort(all(v)); int l = -1, r = 1e9; for (; r - l > 1; ){ int m = (l + r) / 2; if (check(m)) r = m; else l = m; } cout << r; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; while (tt--){ solve(); cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...