제출 #165200

#제출 시각아이디문제언어결과실행 시간메모리
165200johuthaAliens (IOI16_aliens)C++14
4 / 100
2 ms504 KiB
#include "aliens.h" #include <iostream> #include <vector> #include <algorithm> #define int long long using namespace std; struct dpstruct { int n; int k; vector<int> l; vector<int> r; int cost(int a, int b) { b--; int bs = r[b] - l[a] + 1; int ovlp = 0; if (a > 0) ovlp = max(r[a - 1] - l[a] + 1, 0ll); int ret = (bs*bs) - (ovlp*ovlp); // cerr << a << " " << b << " " << bs << " " << ovlp << " " << ret << "\n"; return ret; } int calc() { k = min(k, n); vector<int> dp(n + 1, 1e17); vector<int> olddp(n + 1, 1e17); dp[0] = 0; olddp[0] = 0; for (int i = 0; i < k; i++) { swap(dp, olddp); int curr = 0; for (int j = 1; j <= n; j++) { while (curr < j - 1) { if (olddp[curr] + cost(curr, j) >= olddp[curr + 1] + cost(curr + 1, j)) curr++; else break; } dp[j] = olddp[curr] + cost(curr, j); } /* for (int j : dp) cerr << j << " "; cerr << "\n"; */ } return dp[n]; } }; int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c) { vector<pair<int,int>> prs; for (int i = 0; i < n; i++) { prs.emplace_back(min(r[i], c[i]), -max(r[i], c[i])); } sort(prs.begin(), prs.end()); vector<int> nl; vector<int> nr; nl.push_back(prs[0].first); nr.push_back(-prs[0].second); int last = -prs[0].second; for (int i = 1; i < n; i++) { prs[i].second = -prs[i].second; if (last < prs[i].second) { nl.push_back(prs[i].first); nr.push_back(prs[i].second); } last = max(prs[i].second, last); } dpstruct dps; dps.n = nl.size(); dps.k = k; dps.l = nl; dps.r = nr; return dps.calc(); }
#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...