제출 #1118878

#제출 시각아이디문제언어결과실행 시간메모리
1118878vjudge1Aliens (IOI16_aliens)C++17
25 / 100
64 ms21516 KiB
// #pragma comment(linker, "/stack:200000000") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4") // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt") // #define _GLIBCXX_DEBUG // #define _GLIBCXX_DEBUG_PEDANTIC #ifdef LOCAL #else #include "aliens.h" #endif #include <iomanip> #include <cassert> #include <iostream> #include <vector> #include <random> #include <algorithm> #include <map> #include <set> #include <functional> #include <array> #include <numeric> #include <queue> #include <deque> #include <bitset> #include <cmath> #include <climits> #include <cstdint> // #include <ext/pb_ds/assoc_container.hpp> // #include <ext/pb_ds/tree_policy.hpp> // #include <ext/rope> // using namespace __gnu_pbds; // using namespace __gnu_cxx; using namespace std; const int MOD = 998244353; const long double PI = 3.141592653589793; using ll = long long; const ll INF = 1e18; // #define int ll // --------> sashko123`s defines: #define itn int //Vasya sorry :( #define p_b push_back #define fi first #define se second #define pii std::pair<int, int> #define oo LLONG_MAX #define big INT_MAX #define elif else if int input() { int x; cin >> x; return x; } // ----------> end of sashko123`s defines (thank you Vasya <3) // template<typename K, typename V> // using hash_table = cc_hash_table<K, V, hash<K>>; // template<typename T> // using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; template<typename T> struct li_chao_tree { const T MX = 1e9 + 1; struct line { T k = 0; T b = -INF; T f(T x) const { return k * x + b; } }; struct node { line ln; node* left = nullptr; node* right = nullptr; }; node* new_node() { const int N = 100000; static node* block; static int count = N; if (count == N) { block= new node[N]; count = 0; } return (block + count++); }; node* root = new_node(); T get(T x) { return -get(root, -MX, MX, x); } void add(line ln) { ln.b *= -1; ln.k *= -1; add(root, -MX, MX, ln); } T get(node*& v, T l, T r, T x) { if (!v || l > r) { return -INF; } T ans = v->ln.f(x); if (r == l) { return ans; } T mid = (r + l) / 2; if (x <= mid) { return max(ans, get(v->left, l, mid, x)); } else { return max(ans, get(v->right, mid + 1, r, x)); } } void add(node*& v, T l, T r, line ln) { if (l > r) return; if (!v) { v = new_node(); } T m = (r + l) / 2; bool left = v->ln.f(l) < ln.f(l); bool md = v->ln.f(m) < ln.f(m); if (md) swap(v->ln, ln); if (l == r) { return; } if (left != md) { add(v->left, l, m, ln); } else { add(v->right, m + 1, r, ln); } } }; vector<pii> a; const int N = 600; const int K = 600; ll dp[N][K]; ll W(ll l, ll r) { if (r - l >= 0) return (r - l) * (r - l); return 0ll; } vector<pii> recalc(vector<pii> a, int n) { sort(a.begin(), a.end(), [&](pii x, pii y) { return tuple{x.second, -x.first} < tuple{y.second, -y.first}; }); set<pii> st; for (int i = 0; i < n; i++) { auto [l, r] = a[i]; while (!st.empty() && st.rbegin()->first >= l) { st.erase(prev(st.end())); } st.insert({l, r}); } return vector(st.begin(), st.end()); } ll take_photos(int n, int m, int k, vector<int> rr, vector<int> cc) { a.resize(n); for (int i = 0; i < n; i++) { int r = rr[i], c = cc[i]; if (r > c) swap(r, c); a[i] = {r, c}; } a = recalc(a, n); n = a.size(); for (int i = 0; i < n; i++) a[i].first--; a.insert(a.begin(), {0, 0}); dp[0][0] = 0; for (int c = 1; c <= k; c++) { li_chao_tree<ll> ch; ch.add({.k = -2 * a[1].first, .b = dp[0][c - 1] + a[1].first * a[1].first}); for (int i = 1; i <= n; i++) { dp[i][c] = ch.get(a[i].second) + a[i].second * a[i].second; // cerr << c << " " << i << " " << dp[i][c] << endl; if (i + 1 <= n && c > 1) { ll k = -2 * a[i + 1].first; ll b = dp[i][c - 1] - W(a[i + 1].first, a[i].second) + a[i + 1].first * a[i + 1].first; ch.add({k, b}); } } } return dp[n][k]; } #ifdef LOCAL int32_t main(int32_t argc, const char * argv[]) { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); // insert code here... int n, m, k; cin >> n >> m >> k; vector<int> rr(n); vector<int> cc(n); for (int i = 0; i < n; i++) cin >> rr[i] >> cc[i]; cout << take_photos(n, m, k, rr, cc); return 0; } #endif
#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...