제출 #636633

#제출 시각아이디문제언어결과실행 시간메모리
636633gromperenAliens (IOI16_aliens)C++14
0 / 100
1 ms340 KiB
#include <bits/stdc++.h> #include "aliens.h" #define ll long long #define int long long using namespace std; const int INF = 1e18; int sqr(int x) {return x * x;} long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) { vector<pair<int,int>> tmpcords; vector<pair<int,int>> cords; for (int i = 0; i < n; ++i) { tmpcords.push_back({min(r[i], c[i]), max(r[i], c[i])}); } sort(tmpcords.begin(), tmpcords.end(), [](pair<int,int>a,pair<int,int>b) {return a.first<b.first || (a.first==b.first && a.second>b.second);}); for (auto i : tmpcords) { if (cords.size() && cords.back().second >= i.second) continue; cords.push_back(i); } n = cords.size(); k = min(k, n); //cout << "DBG" << endl; //for (int i =0 ;i < n; ++i) { //cout << cords[i].first << " " << cords[i].second << "\n"; //} auto cost = [&](int i, int j) { // area of photo - overlap if (i == 0) return sqr(cords[j].second - cords[i].first + 1); else return sqr(cords[j].second - cords[i].first + 1) - max(0LL, sqr(cords[i-1].second - cords[i].first + 1)); }; vector<vector<int>> dp(n+5, vector<int>(k+5, INF)); vector<vector<int>> opt(n+5, vector<int>(k+5, INF)); for (int i = 0; i < n; ++i) { //opt[i][i] = i; // if you have n == k then optimum is to take picture of every segment opt[i][1] = 0; // if you have 1 picture optimum is to start at 0 dp[i][1] = cost(0, i); } //dp[0][0] = 0; //for (int i = 0;i <= k; ++i) dp[0][i] = 0; for (int i = n-1; i >= 0; --i) { for (int j =2; j <= k; ++j) { opt[n][j] = n-1; dp[i][j] = dp[i][j-1]; for (int p = opt[i][j-1]; p <= opt[i+1][j]; ++p) { int cur = dp[p][j-1] + cost(p+1, i); //int cur = dp[p][j-1] + sqr(cords[i-1].second - cords[p].first + 1); //if ((p -1 >= 0) && cords[p-1].second >= cords[p].first) //cur -= sqr(cords[p-1].second - cords[p].first + 1); if (cur < dp[i][j]) { opt[i][j] = p; dp[i][j] = cur; } //cout << cur << " "; //cout << cur << endl; //= min(dp[i][j], cur); } } } //for (int i =0; i<=n;++i) { //for (int j = 0; j<=k;++j) { //cout << dp[i][j] << " "; //} //cout << "\n"; //} int ans = INF; for (int i = 0; i <= k; ++i) { ans = min(ans, dp[n-1][i]); } return ans; }
#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...