Submission #420963

#TimeUsernameProblemLanguageResultExecution timeMemory
420963HegdahlAliens (IOI16_aliens)C++17
0 / 100
1 ms332 KiB
#include <bits/stdc++.h> #include "aliens.h" #define ar array using namespace std; using ll = long long; int n; vector<ar<ll, 2>> p; vector<ll> ul, dr; ar<ll, 2> go(ll penalty) { ll total_cost = 0; ll total_used = 1; ll cur_ul = ul[0], cur_dr = dr[0]; ll cur_w = cur_dr-cur_ul+1; ll cur_cost = cur_w*cur_w; for (int i = 1; i < n; ++i) { ll extend_ul = min(cur_ul, ul[i]); ll extend_dr = max(cur_dr, dr[i]); ll extend_w = extend_dr - extend_ul + 1; ll extend_cost = extend_w*extend_w - cur_cost; ll new_w = dr[i]-ul[i]+1; ll new_cost = new_w*new_w + penalty; if (extend_cost < new_cost) { cur_cost += extend_cost; cur_ul = extend_ul; cur_dr = extend_dr; cur_w = extend_w; } else { total_cost += cur_cost; ++total_used; cur_cost = new_cost; cur_ul = ul[i]; cur_dr = dr[i]; cur_w = new_w; } } total_cost += cur_cost; return {total_cost, total_used}; } long long take_photos(int n_, int m, int k, vector<int> r, vector<int> c) { n = n_; p.resize(n); ul.resize(n); dr.resize(n); for (int i = 0; i < n; ++i) p[i] = {r[i], c[i]}; sort(p.begin(), p.end(), [&](auto a, auto b) { return a[0]+a[1] < b[0]+b[1]; }); for (int i = 0; i < n; ++i) ul[i] = min(p[i][0], p[i][1]); for (int i = 0; i < n; ++i) dr[i] = max(p[i][0], p[i][1]); /* cerr << "ul: "; for (int i = 0; i < n; ++i) cerr << ul[i] << " \n"[i==n-1]; cerr << "dr: "; for (int i = 0; i < n; ++i) cerr << dr[i] << " \n"[i==n-1]; // */ const ll INF = 1LL<<60; ll lo = 0, hi = INF; while (lo != hi) { ll ce = lo + (hi-lo)/2; auto [cost, used] = go(ce); if (used > k) lo = ce+1; else hi = ce; } auto [cost, used] = go(lo); cost -= (used-1)*lo; 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...