Submission #1005409

#TimeUsernameProblemLanguageResultExecution timeMemory
1005409rahidilbayramliWatching (JOI13_watching)C++17
100 / 100
264 ms31064 KiB
#pragma GCC optimize("-O3") #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define ll long long #define ld long double #define vl vector<ll> #define vi vector<int> #define pii pair<int, int> #define pll pair<ll, ll> #define all(v) v.begin(), v.end() #define rall(v) v.rbegin(), v.rend() #define pb push_back #define p_b pop_back #define f first #define s second using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll sz = 2e3+5; ll a[sz], dp[sz][sz], n, p, q; ll lst(ll pos, ll mid) { ll g = a[pos + 1] + mid - 1; ll l = pos + 1, r = n - 1, res = pos; while(l <= r) { ll mid = (l + r) / 2; if(a[mid] <= g) { res = max(res, mid); l = mid + 1; } else r = mid - 1; } return res; } bool ch(ll mid) { dp[0][0] = -1; for(ll i = 0; i <= p; i++) { for(ll j = 0; j <= q; j++) { if(i == 0 && j == 0) continue; if(i == 0) dp[i][j] = lst(dp[i][j-1], mid * 2); else if(j == 0) dp[i][j] = lst(dp[i-1][j], mid); else dp[i][j] = max(lst(dp[i-1][j], mid), lst(dp[i][j-1], mid * 2)); if(dp[i][j] == n - 1) return true; } } return false; } void solve() { ll i, j; cin >> n >> p >> q; for(i = 0; i < n; i++) cin >> a[i]; sort(a, a+n); if(p + q >= n) { cout << "1\n"; return; } ll l = 1, r = a[n-1], ans; while(l <= r) { ll mid = (l + r) / 2; if(ch(mid)) { ans = mid; r = mid - 1; } else l = mid + 1; } cout << ans << "\n"; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll tests = 1; //cin >> tests; while(tests--) { solve(); } }

Compilation message (stderr)

watching.cpp: In function 'void solve()':
watching.cpp:63:11: warning: unused variable 'j' [-Wunused-variable]
   63 |     ll i, j;
      |           ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...