제출 #330560

#제출 시각아이디문제언어결과실행 시간메모리
330560IgorIAliens (IOI16_aliens)C++17
0 / 100
1 ms384 KiB
#include <bits/stdc++.h> #include "aliens.h" using namespace std; void solve(int i, vector<int> &l, vector<int> &r, vector<vector<long long> > &dp, int le_g, int ri_g, int le_p, int ri_p) { if (le_g > ri_g) return; int mid_g = (le_g + ri_g) / 2; int id = le_p; for (int p = le_p; p <= ri_p; p++) { long long res = dp[p][mid_g - 1]; long long L = l[p], R = r[i - 1], covto = -1; if (p) covto = r[p - 1]; if (covto < L) res += 1ll * (R - L + 1) * (R - L + 1); else res += 1ll * (R - L + 1) * (R - L + 1) - 1ll * (covto - L + 1) * (covto - L + 1); if (res < dp[i][mid_g]) { id = p; dp[i][mid_g] = res; } } solve(i, l, r, dp, le_g, mid_g - 1, le_p, id); solve(i, l, r, dp, mid_g + 1, ri_g, id, ri_p); } long long take_photos(int n, int m, int k, vector<int> l, vector<int> r) { vector<int> cv(m); for (int i = 0; i < m; i++) { cv[i] = i + 1; } for (int i = 0; i < n; i++) { int x = min(l[i], r[i]); int y = max(l[i], r[i]); cv[y] = min(cv[y], x); } l.clear(); r.clear(); for (int i = 0; i < m; i++) { if (cv[i] <= i) { while (l.size() && l.back() >= cv[i]) l.pop_back(), r.pop_back(); l.push_back(cv[i]), r.push_back(i); } } n = l.size(); const long long INFLL = 1e18; vector<vector<long long> > dp(n + 1, vector<long long>(k + 1, INFLL)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { solve(i, l, r, dp, 1, k, 0, i - 1); } return *min_element(dp[n].begin(), dp[n].end()); }
#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...