제출 #639647

#제출 시각아이디문제언어결과실행 시간메모리
639647pls33Aliens (IOI16_aliens)C++17
60 / 100
2094 ms364496 KiB
#include "aliens.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #pragma region dalykai using p32 = pair<int, int>; using p32u = pair<uint32_t, uint32_t>; using p64 = pair<int64_t, int64_t>; using p64u = pair<uint64_t, uint64_t>; using vi16 = vector<int16_t>; using vi16u = vector<uint16_t>; using vi32 = vector<int>; using vi32u = vector<uint32_t>; using vi64 = vector<int64_t>; using vi64u = vector<uint64_t>; using vp32 = vector<p32>; using vp32u = vector<p32u>; using vp64 = vector<p64>; using vp64u = vector<p64u>; using vvi32 = vector<vi32>; using vvi32u = vector<vi32u>; using vvi64 = vector<vi64>; using vvi64u = vector<vi64u>; using vvp32 = vector<vp32>; using vvp32u = vector<vp32u>; using vvp64 = vector<vp64>; using vvp64u = vector<vp64u>; using pf32 = pair<float, float>; using pf64 = pair<double, double>; using pf80 = pair<long double, long double>; using vf32 = vector<float>; using vf64 = vector<double>; using vf80 = vector<long double>; using vpf32 = vector<pf32>; using vpf64 = vector<pf64>; using vpf80 = vector<pf80>; using vvf32 = vector<vf32>; using vvf64 = vector<vf64>; using vvf80 = vector<vf80>; using vvpf32 = vector<vpf32>; using vvpf64 = vector<vpf64>; using vvpf80 = vector<vpf80>; using fl80_t = long double; template <typename key, typename val> using ord_map = tree<key, val, less<key>, rb_tree_tag, tree_order_statistics_node_update>; template <typename key> using ord_set = tree<key, null_type, less<key>, rb_tree_tag, tree_order_statistics_node_update>; #pragma endregion struct line_t { int64_t k, m, p; bool operator<(const line_t &o) const { return k < o.k; } bool operator<(int64_t x) const { return p < x; } long long eval(long long x) const { return k * x + m; } }; struct cht_t { deque<line_t> hull; int64_t div(int64_t a, int64_t b) { return floor(double(a) / b); } bool intersect(line_t &x, const line_t &y) { if (x.k == y.k) { x.p = x.m > y.m ? INT64_MAX : INT64_MIN; } else { x.p = div(y.m - x.m, x.k - y.k); } return x.p >= y.p; } void add(long long k, long long m) { line_t line = {k, m, 0}; // wtf? while (hull.size() >= 2 && (intersect(line, hull.back()), intersect(hull.back(), hull[(int)hull.size() - 2]), line.p < hull.back().p)) { hull.pop_back(); } hull.push_back(line); } int64_t query(int64_t x) { if (!hull.size()) { return INT64_MAX; } while (hull.size() >= 2 && hull[0].eval(x) >= hull[1].eval(x)) { hull.pop_front(); } return hull[0].eval(x); } }; void insert(int64_t left, int64_t tiles, cht_t &cht) { int64_t slope = 2 - 2 * left; int64_t offset = (left - 1) * (left - 1) + tiles; cht.add(slope, offset); } int64_t query(int64_t val, cht_t &cht) { int64_t y = cht.query(val); return (y == INT64_MAX) ? INT64_MAX : y + val * val; } int64_t cost(p64 range) { assert(range.first <= range.second); return (range.second - range.first + 1) * (range.second - range.first + 1); } long long take_photos(int n, int m, int k, vi32 r, vi32 c) { vp32 range(n); for (int i = 0; i < n; i++) { if (c[i] > r[i]) { swap(c[i], r[i]); } range[i] = {c[i], r[i]}; } sort(range.begin(), range.end(), [](p32 a, p32 b) { return (a.first == b.first) ? a.second > b.second : a.first < b.first; }); int cur_max = -1; vp32 selected; for (auto &r : range) { if (r.second > cur_max) { selected.push_back(r); cur_max = r.second; } } vvi64 tile(selected.size(), vi64(k + 1, INT64_MAX)); vector<cht_t> cht(k + 1); tile[0][1] = cost(selected[0]); insert(selected[0].first, 0, cht[1]); for (size_t point = 1; point < tile.size(); point++) { for (size_t count = 1; count <= min(point + 1, size_t(k)); count++) { int64_t &cur = tile[point][count]; int64_t &prev = tile[point - 1][count - 1]; p32 a = selected[point]; p32 b = selected[point - 1]; cur = min(cur, query(a.second, cht[count])); if (prev != INT64_MAX) { int64_t val = prev + cost(a); if (a.first <= b.second) { val -= cost({a.first, b.second}); } cur = min(cur, val); } if (cur != INT64_MAX) { int64_t tiles = tile[point - 1][count - 1]; if (a.first <= b.second) { tiles -= cost({a.first, b.second}); } insert(a.first, tiles, cht[count]); } } } int64_t result = *min_element(tile.back().begin(), tile.back().end()); return result; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp:9: warning: ignoring '#pragma region dalykai' [-Wunknown-pragmas]
    9 | #pragma region dalykai
      | 
aliens.cpp:57: warning: ignoring '#pragma endregion ' [-Wunknown-pragmas]
   57 | #pragma endregion
      |
#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...