제출 #922325

#제출 시각아이디문제언어결과실행 시간메모리
922325denniskimAliens (IOI16_aliens)C++17
4 / 100
90 ms179428 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; typedef pair<ll, ll> pll; typedef pair<ld, ld> pld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10); #define sp << " " #define en << "\n" #define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end()) ll n, m, k; pll a[100010]; ll dp[110][100010]; ll gyo[100010]; struct line { ll A, B; ld S; }; ld intersect(ll A1, ll B1, ll A2, ll B2) { return (ld)(B2 - B1) / (ld)(A1 - A2); } struct CHT { vector<line> lin; void init(void) { lin.clear(); } void update(ll X, ll Y) { while(!lin.empty()) { if(intersect(lin.back().A, lin.back().B, X, Y) < lin.back().S) lin.pop_back(); else break; } if(lin.empty()) { lin.push_back({X, Y, -INF}); return; } lin.push_back({X, Y, intersect(lin.back().A, lin.back().B, X, Y)}); } ll query(ll X) { ll l = 0, r = (ll)lin.size() - 1; while(l <= r) { ll mid = (l + r) >> 1; if(lin[mid].S <= X) l = mid + 1; else r = mid - 1; } return lin[r].A * X + lin[r].B; } }cht; void solve(void) { for(ll i = 1 ; i <= n ; i++) dp[0][i] = m * m + 1; for(ll i = 1 ; i <= k ; i++) { cht.init(); cht.update(-2 * (a[1].fi - 1), (a[1].fi - 1) * (a[1].fi - 1)); for(ll j = 1 ; j <= n ; j++) { dp[i][j] = cht.query(a[j].se) + a[j].se * a[j].se; if(j < n) cht.update(-2 * (a[j + 1].fi - 1), dp[i - 1][j] + (a[j + 1].fi - 1) * (a[j + 1].fi - 1) - gyo[j]); } } } long long take_photos(int N, int M, int K, std::vector<int> R, std::vector<int> C) { vector<pll> vec; n = N, m = M, k = K; for(ll i = 0 ; i < n ; i++) a[i + 1] = {R[i] + 1, C[i] + 1}; for(ll i = 1 ; i <= n ; i++) { if(a[i].fi > a[i].se) swap(a[i].fi, a[i].se); } sort(a + 1, a + 1 + n); for(ll i = 2 ; i <= n ; i++) { if(a[i].fi != a[i - 1].fi) vec.push_back(a[i - 1]); } vec.push_back(a[n]); ll maxx = 0; n = 0; for(auto &i : vec) { if(i.se > maxx) { maxx = i.se; a[++n] = i; } } for(ll i = 1 ; i < n ; i++) { ll w1 = a[i + 1].fi, w2 = a[i].se; if(w2 < w1) gyo[i] = 0; else gyo[i] = (w2 - w1 + 1) * (w2 - w1 + 1); } solve(); ll ans = INF; for(ll i = 1 ; i <= k ; i++) ans = min(ans, dp[i][n]); return ans; }
#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...