제출 #799787

#제출 시각아이디문제언어결과실행 시간메모리
799787NeroZeinAliens (IOI16_aliens)C++17
12 / 100
128 ms2316 KiB
#include "aliens.h" #include "bits/stdc++.h" using namespace std; const int N = 503; const long long INF = 1e15; long long dp[N][N]; long long bt (int id, int rem, const vector<pair<int, int>>& pts, const int& n, const int& m) { if (rem < 0) { return INF; } if (id == n) { return 0; } long long& ret = dp[id][rem]; if (ret != -1) { return ret; } ret = INF; int mn = m, mx = -m; for (int j = id; j < n; ++j) { auto [r, c] = pts[j]; mn = min({mn, r, c}); mx = max({mx, r, c}); ret = min(ret, bt(j + 1, rem - 1, pts, n, m) + (mx - mn + 1) * (mx - mn + 1)); } return ret; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<pair<int, int>> pts(n); for (int i = 0; i < n; ++i) { pts[i] = {r[i], c[i]}; } sort(pts.begin(), pts.end(), [&](pair<int,int> i, pair<int,int> j) { return max(i.first, i.second) < max(j.first, j.second); }); memset(dp, -1, sizeof dp); return bt(0, k, pts, n, m); }
#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...