제출 #115134

#제출 시각아이디문제언어결과실행 시간메모리
115134E869120Aliens (IOI16_aliens)C++14
60 / 100
990 ms130808 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; struct Node { long long l, r, a, b; }; bool operator<(const Node &a1, const Node &a2) { if (a1.l < a2.l) return true; if (a1.l > a2.l) return false; if (a1.r < a2.r) return true; if (a1.r > a2.r) return false; return false; } class ConvexHullTrick { public: vector<Node> vec; void init() { vec.clear(); vec.push_back(Node{-(1LL<<62), (1LL<<62), -1LL, (1LL<<60)}); } long long cross_point(Node p1, Node p2) { // 最後に p1 が勝つ点を求める long long E = (p2.a - p1.a) * (p2.a - p1.a) + p2.b - p1.b; long long S = 0; if (E >= 0) S = E / (2LL * (p2.a - p1.a)); else { S = (-E) / (2LL * (p2.a - p1.a)); S *= -1LL; S--; } return S + p1.a; } void add(long long pa, long long pb) { while (true) { Node V = vec[vec.size() - 1]; long long C = cross_point(V, Node{-(1LL<<62), (1LL<<62), pa, pb}); if (C < V.l) { vec.pop_back(); } else { vec[vec.size() - 1].r = C; vec.push_back(Node{C + 1LL, (1LL << 62), pa, pb}); break; } } } long long getmax(long long pos) { int pos1 = lower_bound(vec.begin(), vec.end(), Node{pos + 1LL, -(1LL << 62), 0LL, 0LL}) - vec.begin(); pos1--; return (pos - vec[pos1].a) * (pos - vec[pos1].a) + vec[pos1].b; } }; long long G[1 << 20]; vector<pair<int, int>> V; ConvexHullTrick E; vector<long long>dp[50009]; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for (int i = 0; i <= n; i++) dp[i].resize(k + 1, 0LL); for (int i = 0; i < n; i++) { if (r[i] > c[i]) swap(c[i], r[i]); G[r[i]] = max(G[r[i]], 1LL * (c[i] + 1LL)); } long long maxn = 0; for (int i = 0; i < m; i++) { if (G[i] > maxn) { V.push_back(make_pair(i, G[i])); maxn = G[i]; } } for (int i = 0; i <= (int)V.size(); i++) { for (int j = 0; j <= k; j++) dp[i][j] = (1LL << 50); } dp[0][0] = 0; for (int t = 0; t <= k - 1; t++) { E.init(); for (int i = 0; i < (int)V.size(); i++) E.add(V[i].first, dp[i][t]); for (int i = 1; i <= (int)V.size(); i++) { long long F = E.getmax(V[i - 1].second); if (i < (int)V.size()) { long long FF = max(0LL, 1LL * (V[i - 1].second - V[i].first)); F -= FF * FF; } dp[i][t + 1] = F; } } /*for (int i = 0; i <= V.size(); i++) { for (int j = 0; j <= k; j++) printf("% 3d", dp[i][j]); printf("\n"); }*/ long long ans = (1LL << 60); for (int i = 0; i <= k; i++) ans = min(ans, dp[V.size()][i]); 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...