제출 #773982

#제출 시각아이디문제언어결과실행 시간메모리
773982JomnoiAliens (IOI16_aliens)C++17
25 / 100
5 ms4284 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; const int MAX_N = 1e5 + 5; const int MAX_M = 1e6 + 5; const long long INF = 1e18 + 7; int N, M, K; int X[MAX_N], Y[MAX_N]; int minL[MAX_M]; long long divide(long long a, long long b) { return a / b - ((a ^ b) < 0 and a % b != 0); } struct Line { long long m, c; long long dot(long long x) { return m * x + c; } long long intersect(const Line &o) { return divide(o.c - c, m - o.m); } }; struct ConvexHullTrick { deque <Line> dq; void addLine(Line f) { while (dq.size() >= 2 and dq.back().intersect(f) <= dq[dq.size() - 2].intersect(dq.back())) dq.pop_back(); dq.push_back(f); } long long query(long long x) { while (dq.size() >= 2 and dq[0].dot(x) <= dq[1].dot(x)) dq.pop_front(); return dq[0].dot(x); } }; long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) { N = n, M = m, K = k; for (int i = 0; i < m; i++) minL[i] = M; for (int i = 0; i < N; i++) { int x = min(r[i], c[i]), y = max(r[i], c[i]); minL[y] = min(minL[y], x); } stack <pair <int, int>> stk; for (int i = 0; i < m; i++) { if (minL[i] == M) continue; while (!stk.empty() and stk.top().first >= minL[i]) stk.pop(); stk.emplace(minL[i], i); } N = n = stk.size(); while (!stk.empty()) { auto [x, y] = stk.top(); stk.pop(); X[n] = x, Y[n] = y; n--; } X[N + 1] = Y[N + 1] = M; vector <vector <long long>> dp(K + 1, vector <long long>(N + 1, INF)); dp[0][0] = 0; for (int k = 1; k <= K; k++) { ConvexHullTrick cht; for (int i = 1; i <= N; i++) { long long overlap = 1ll * max(0, Y[i] - X[i + 1] + 1) * max(0, Y[i] - X[i + 1] + 1); cht.addLine({2 * X[i], -X[i] * X[i] - dp[k - 1][i - 1]}); dp[k][i] = -overlap + (Y[i] + 1) * (Y[i] + 1) - cht.query((Y[i] + 1)); } } long long ans = INF; for (int k = 1; k <= K; k++) ans = min(ans, dp[k][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...