Submission #632783

#TimeUsernameProblemLanguageResultExecution timeMemory
632783rainliofficialAliens (IOI16_aliens)C++14
4 / 100
1 ms340 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } #define sz(x) (int)x.size() const int MAXN = 2e5+5; const ll INF = 1e18; struct Point{ ll r, c, id, cnt; bool operator<(const Point& o) const{ if (r != o.r){ return r < o.r; } return c < o.c; } }; bool byr(const Point& a, const Point& b){ return a.r != b.r ? a.r < b.r : a.c > b.c; // sort by smaller row, then by greater col } bool byc(const Point& a, const Point& b){ return a.c != b.c ? a.c < b.c : a.r > b.r; // smaller col, smaller row } ll sq(ll x){ return x*x; } ll get(pii a, int c){ return a.first * c + a.second; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { // reflect the points under the diag vector<Point> arr; int tot = 0; set<Point> allPoints; for (int i=0; i<n; i++){ if (r[i] > c[i]){ swap(r[i], c[i]); } Point cur = {r[i], c[i], tot, 1}; auto it = allPoints.find(cur); if (it != allPoints.end()){ arr[(*it).id].cnt++; }else{ arr.push_back(cur); allPoints.insert(cur); tot++; } } n = tot; sort(arr.begin(), arr.end(), byr); set<Point, decltype(&byc)> seen(&byc); for (int i=0; i<n; i++){ auto it = seen.lower_bound(arr[i]); if (it == seen.end()){ seen.insert(arr[i]); }else{ // Point upd = *it; // upd.cnt++; // seen.erase(it); // seen.insert(upd); } } arr.clear(); for (Point x : seen){ // cout << x.r << " " << x.c << " " << x.id << " " << x.cnt << "\n"; arr.push_back(x); } n = sz(arr); // run dp vector<vector<ll>> dp(n+1, vector<ll>(k+1, INF)); // dp[i][j] = max cover up to ith point after taking j pictures for (int i=0; i<=k; i++) dp[0][i] = 0; vector<vector<pii>> lines(n+1, vector<pii>(k+1)); vector<int> pj(k+1, 1); for (int i=1; i<=n; i++){ for (int j=1; j<=k; j++){ ll overlap = i > 1 && arr[i-2].c >= arr[i-1].r ? sq(arr[i-2].c - arr[i-1].r + 1) : 0; lines[i][j] = {-2*(arr[i-1].r - 1), sq(arr[i-1].r - 1) + dp[i-1][j-1] - overlap}; while (pj[j] < i && get(lines[pj[j]][j], arr[i-1].c) >= get(lines[pj[j]+1][j], arr[i-1].c)){ pj[j]++; } dp[i][j] = sq(arr[i-1].c) + get(lines[pj[j]][j], arr[i-1].c); // for (int ip=1; ip<=i; ip++){ // ll area = sq(arr[i-1].c - arr[ip-1].r + 1); // ll overlap = ip > 1 && arr[ip-2].c >= arr[ip-1].r ? sq(arr[ip-2].c - arr[ip-1].r + 1) : 0; // ckmin(dp[i][j], dp[ip-1][j-1] + area - overlap); // } } } return dp[n][k]; }
#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...