Submission #421040

#TimeUsernameProblemLanguageResultExecution timeMemory
421040HegdahlAliens (IOI16_aliens)C++17
4 / 100
1 ms292 KiB
#include <bits/stdc++.h> #include "aliens.h" #define ar array using namespace std; using ll = long long; using lll = __int128; using ld = long double; int n, m, k; vector<ar<ll, 2>> p; vector<ll> l, r; vector<int> s; const ll INF = 1LL<<60; ll overlap(ll l0, ll r0, ll l1, ll r1) { assert(l0 <= l1); assert(l0 <= r0); assert(l1 <= r1); // completely inside if (r1 <= r0) return (r1-l1+1)*(r1-l1+1); // completely outside if (r0 < l1) return 0; return (r0-l1+1)*(r0-l1+1); } pair<ll, int> go(ld penalty) { ll real_cost = 0; int used = 0; ll cl = -INF; ll cr = -INF; ld tiebreak = 0; ld tiebreak_inc = .5l/n; for (int i : s) { lll was_w = cr-cl+1; lll extend_w = max(cr, r[i]) - min(cl, l[i]) + 1; lll extend_cost = extend_w*extend_w - was_w*was_w; lll new_w = r[i]-l[i]+1; lll new_cost = new_w*new_w - overlap(cl, cr, l[i], r[i]); if (extend_cost < new_cost + penalty + tiebreak) { real_cost += extend_cost; cl = min(cl, l[i]); cr = max(cr, r[i]); } else { //if (cl > -INF) cerr << cl << ':' << cr << ' '; real_cost += new_cost; cl = l[i]; cr = r[i]; ++used; } tiebreak += tiebreak_inc; } //if (cl > -INF) cerr << cl << ':' << cr << '\n'; return {real_cost, used}; } ll take_photos(int n_, int m_, int k_, vector<int> r_, vector<int> c_) { n = n_, m = m_, k = k_; l.resize(n); r.resize(n); s.resize(n); for (int i = 0; i < n; ++i) { l[i] = min(r_[i], c_[i]); r[i] = max(r_[i], c_[i]); } iota(s.begin(), s.end(), 0); sort(s.begin(), s.end(), [&](int i, int j) { return l[i] < l[j]; }); ld lo = 0, hi = 1e18; while (hi-lo > 1e-7) { ld ce = (hi+lo)/2; auto [cost, cnt] = go(ce); if (cnt > k) lo = ce; else hi = ce; } auto [cost, cnt] = go(hi); return cost; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...