Submission #839291

#TimeUsernameProblemLanguageResultExecution timeMemory
839291hafoWatching (JOI13_watching)C++14
100 / 100
159 ms16068 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define pb push_back #define pa pair<int, int> #define pall pair<ll, int> #define fi first #define se second #define TASK "test" #define Size(x) (int) x.size() #define all(x) x.begin(), x.end() using namespace std; template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;} template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;} const int MOD = 1e9 + 7; const int LOG = 20; const int maxn = 2e3 + 7; const ll oo = 1e9 + 69; int n, p, q, a[maxn], dp[maxn][maxn]; bool check(int w) { for(int i = 1; i <= n; i++) { int l1 = lower_bound(a + 1, a + 1 + n, a[i] - w + 1) - a; int l2 = lower_bound(a + 1, a + 1 + n, a[i] - 2 * w + 1) - a; for(int j = 0; j <= p; j++) { dp[i][j] = oo; if(j > 0) mini(dp[i][j], dp[l1 - 1][j - 1]); mini(dp[i][j], dp[l2 - 1][j] + 1); if(i == n && dp[i][j] <= q) return 1; } } return 0; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); //freopen(TASK".inp", "r", stdin); //freopen(TASK".out", "w", stdout); cin>>n>>p>>q; mini(p, n); mini(q, n); for(int i = 1; i <= n; i++) cin>>a[i]; sort(a + 1, a + 1 + n); int l = 1, r = 1e9, mid, res; while(l <= r) { mid = l + r >> 1; if(check(mid)) { res = mid; r = mid - 1; } else l = mid + 1; } cout<<res; return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         mid = l + r >> 1;
      |               ~~^~~
watching.cpp:59:11: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     cout<<res;
      |           ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...