Submission #631849

#TimeUsernameProblemLanguageResultExecution timeMemory
631849rainliofficialAliens (IOI16_aliens)C++17
0 / 100
0 ms212 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> 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, INF = 1e9; struct Point{ int 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 } int getArea(Point a, Point b){ int area = (abs(b.r - b.c) + 1) * (abs(b.r - b.c) + 1); int overlap = a.c - b.r + 1; if (overlap*overlap == area){ return area; // a == b } if (overlap <= 0){ return area; }else{ return area - overlap*overlap; } } 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<int>> dp(n+1, vector<int>(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; for (int i=1; i<=n; i++){ for (int j=1; j<=k; j++){ for (int ip=1; ip<=i; ip++){ ckmin(dp[i][j], dp[i-1][j-1] + getArea(arr[ip-1], arr[i-1])); } } } return dp[n][k]; } /** * Debugging checklist: * - Reset everything after each TC * - Integer overflow, index overflow * - Special cases? */
#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...