Submission #529480

#TimeUsernameProblemLanguageResultExecution timeMemory
529480msg555Aliens (IOI16_aliens)C++14
60 / 100
2065 ms13208 KiB
#include "aliens.h" #include <vector> #include <algorithm> #include <iostream> #include <set> #include <cassert> using namespace std; long long squared(int x) { return 1ll * x * x; } template<typename T> struct line_elem { T a; T b; T x_start; bool point_query; line_elem() : a(0), b(0), x_start(0), point_query(false) {} line_elem(T x) : a(0), b(0), x_start(x), point_query(true) {} line_elem(T a, T b, T x_start = 0) : a(a), b(b), x_start(x_start), point_query(false) {} T get(T x) const { return a * x + b; } bool operator<(const line_elem& rhs) const { if (point_query || rhs.point_query) { return x_start < rhs.x_start; } return make_pair(a, b) < make_pair(rhs.a, rhs.b); } bool operator<(const pair<T, T>& rhs) const { return make_pair(a, b) < rhs; } bool operator<(T x) const { return x_start < x; } }; template<typename T> T cross_x(const line_elem<T>& X, const line_elem<T>& Y) { /* Returns the first x >= to when the lines intersect */ T da = X.a - Y.a; T db = Y.b - X.b; assert(da != 0); if (da < 0) { da = -da; db = -db; } if (db < 0) { return db / da; } return (db + da - 1) / da; } template<typename T> struct line_hull { /* Implements a max hull, get the max ax+b for all inserted lines. */ bool insert(T a, T b) { /* Insert line ax+b */ auto ln = line_elem<T>(a, b); auto it = st.lower_bound(ln); bool is_last = it == st.end(); if (!is_last && ln.a == it->a) { return false; } auto jt = it; bool is_first = it == st.begin(); if (!is_first) { --it; if (it->a == ln.a) { if (it == st.begin()) { is_first = true; } else { --it; } } } T lft_x = is_first ? numeric_limits<T>::min() : cross_x(*it, ln); T rht_x = is_last ? numeric_limits<T>::max() : cross_x(ln, *jt); if (rht_x <= lft_x) { return false; } if (!is_first) { while (it != st.begin()) { auto kt = it--; T prev_lft_x = cross_x(*it, *kt); if (prev_lft_x < lft_x) { ++it; break; } lft_x = cross_x(*it, ln); } ++it; } if (!is_last) { while (true) { auto kt = jt++; if (jt == st.end()) { break; } T prev_rht_x = cross_x(*kt, *jt); if (rht_x < prev_rht_x) { break; } rht_x = cross_x(ln, *jt); } --jt; } line_elem<T> new_rht; if (!is_last) { new_rht = *jt++; } st.erase(it, jt); st.insert(line_elem<T>(a, b, lft_x)); if (!is_last) { new_rht.x_start = rht_x; st.insert(new_rht); } return true; } T get(T x) const { auto it = st.upper_bound(x); --it; return it->get(x); } set<line_elem<T> > st; }; long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) { vector<pair<int, int> > A; for (int i = 0; i < N; i++) { int ri = R[i]; int ci = C[i]; if (ri > ci) swap(ri, ci); A.push_back(make_pair(ci, ci - ri)); } sort(A.begin(), A.end()); int j = 0; for (auto p : A) { while (j > 0 && p.second >= A[j - 1].second + p.first - A[j - 1].first) { --j; } A[j++] = p; } A.resize(j); N = j; vector<long long> ADJ(N + 1, 0); for (int i = 1; i < N; i++) { ADJ[i] = squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first)); } long long INF = squared(M + 1); vector<long long> DP(N + 1, INF); vector<long long> DP2(N + 1, INF); DP[0] = 0; DP2[0] = 0; for (int k = 0; k < K; k++) { line_hull<long long> hl; for (int i = 0; i <= N; i++) { if (i) { long long x = A[i - 1].first; DP2[i] = -hl.get(x) + squared(x); } /* for (int j = 0; j < i; j++) { DP[i] = min( DP[i], DP[j] + squared(1 + A[j].second + A[i - 1].first - A[j].first) - ADJ[j] ); } */ // x^2 + bx + c where x = A[i - 1].first long long sadd = 1 + A[i].second - A[i].first; long long b = 2 * sadd; long long c = squared(sadd) + DP[i] - ADJ[i]; hl.insert(-b, -c); } DP.swap(DP2); } return DP[N]; }
#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...