Submission #1114910

#TimeUsernameProblemLanguageResultExecution timeMemory
1114910mat_jurAliens (IOI16_aliens)C++17
60 / 100
1296 ms1048576 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;} auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";} #define debug(X) cerr << "["#X"]: " << X << '\n'; #else #define cerr if(0)cout #define debug(X) ; #endif using ll = long long; using ld = long double; #define all(v) (v).begin(), (v).end() #define ssize(x) int(x.size()) #define fi first #define se second #define mp make_pair #define eb emplace_back const ll inf = 1e15; ll sq(int x) { return ll(x)*x; } struct line { ll a, b; line(ll x = 0, ll y = 0): a(x), b(y) {} }; ld intersection(line l1, line l2) { assert(l1.a != l2.a); return ld(l2.b - l1.b) / ld(l1.a - l2.a); } struct CHT { deque<line> q; CHT() {} void add(line l) { while (ssize(q) >= 2 && intersection(l, q[ssize(q)-2]) <= intersection(q[ssize(q)-2], q[ssize(q)-1])) q.pop_back(); q.eb(l); } ll query(ll x) { if (!ssize(q)) return inf; while (ssize(q) >= 2 && x >= intersection(q[0], q[1])) q.pop_front(); return q[0].a * x + q[0].b; } }; long long take_photos(int n, int m, int k, std::vector<int> x, std::vector<int> y) { for (int i = 0; i < n; ++i) if (x[i] > y[i]) swap(x[i], y[i]); debug(x); debug(y); vector<int> nx, ny; vector<int> idx(n); iota(all(idx), 0); sort(all(idx), [&](int a, int b) { return mp(y[a], x[a]) > mp(y[b], x[b]); }); debug(idx); int mx = m+1; for (int i : idx) { if (mx <= x[i]) continue; debug(i); debug(mx); debug(mp(x[i], y[i])); nx.eb(x[i]); ny.eb(y[i]); mx = x[i]; } n = ssize(nx); x = nx; y = ny; reverse(all(x)); reverse(all(y)); debug(n); debug(x); debug(y); debug(inf); vector<vector<ll>> dp(n+1, vector<ll>(k+1, inf)); dp[0][0] = 0; for (int j = 1; j <= k; ++j) { CHT cht; for (int i = 1; i <= n; ++i) { cht.add(line(-2 * (x[i-1]-1), sq(x[i-1]-1) + dp[i-1][j-1] - (i - 2 >= 0 ? sq(max(0, y[i-2] - x[i-1]+1)) : 0ll) )); dp[i][j] = sq(y[i-1]) + cht.query(y[i-1]); // for (int l = 0; l < i; ++l) { // dp[i][j] = min(dp[i][j], dp[l][j-1] + sq(y[i-1] - x[l] + 1) - (l - 1 >= 0 ? sq(max(0, y[l-1] - x[l]+1)) : 0ll) ); // } } } debug(dp); ll res = inf; for (int j = 0; j <= k; ++j) res = min(res, dp[n][j]); return res; } #ifdef LOCAL int main() { int n, m, k; assert(3 == scanf("%d %d %d", &n, &m, &k)); std::vector<int> r(n), c(n); for (int i = 0; i < n; i++) { assert(2 == scanf("%d %d", &r[i], &c[i])); } long long ans = take_photos(n, m, k, r, c); printf("%lld\n", ans); } #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...