Submission #784283

#TimeUsernameProblemLanguageResultExecution timeMemory
784283baneWatching (JOI13_watching)C++17
100 / 100
89 ms15984 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") /* #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; */ #ifdef LOCAL #include "algo/debug.h" #else #define debug(...) 42 #endif #define fr first #define sc second #define pb push_back #define mp make_pair #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define endl '\n' using ll = long long; using ld = long double; using pii = pair<int,int>; using pll = pair<ll,ll>; const int MOD = (int)1e9 + 7; const int dx[4] = {1,-1,0,0}; const int dy[4] = {0,0,1,-1}; const int maxN = (int)2e5+1; int n, p, q; int a[2001]; bool check(int w){ int dp[n+1][q + 1]; for (int i = 0; i <= n; i++){ for (int j = 0; j <= q; j++){ dp[i][j] = (int)1e9; } } dp[0][0] = 0; for (int R = 1; R <= n; R++){ int pos2 = R, pos1 = R; for (int L = R; L>=1; L--){ if (a[R] - a[L] <= w - 1)pos1 = L; if (a[R] - a[L] <= 2 * w - 1)pos2 = L; if (a[R] - a[L] >= 2 * w)break; } for (int j = 0; j <= q; j++){ if (j) dp[R][j] = min(dp[pos2-1][j - 1], dp[R][j]); dp[R][j] = min(dp[R][j], dp[pos1-1][j]+1); } } int MIN = (int)1e9; for (int i = 0; i <= q; i++)MIN = min(MIN, dp[n][i]); return MIN <= p; } void Ormnis(){ cin >> n >> p >> q; q = min(n,q); for (int i = 1; i <= n; i++){ cin >> a[i]; } sort(a + 1, a + 1 + n); int l = 1, r = (int)a[n] - a[1]; while(l<=r){ int mid = (l+r) >> 1; if (check(mid)) r = mid - 1; else l = mid + 1; } cout << r + 1 << endl; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int tt = 1; //cin >> tt; while(tt--){ Ormnis(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...