제출 #140680

#제출 시각아이디문제언어결과실행 시간메모리
140680SortingAliens (IOI16_aliens)C++14
60 / 100
395 ms44520 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; const int N = 5e4 + 7; const int K = 107; const long long inf = 1e18; bool cmp(pair<long long, long long> lvalue, pair<long long, long long> rvalue){ if(lvalue.first != rvalue.first){ return lvalue.first < rvalue.first; } return lvalue.second > rvalue.second; } pair<long long, long long> p[N]; long long dp[N][K]; long long calc_dp(int pos, int left){ if(pos < 0){ return 0; } return dp[pos][left]; } void solve(int l, int r, int l2, int r2, int k){ if(l > r){ return; } int mid = (l + r) >> 1, ptr = -1; dp[mid][k] = inf; for(int i = min(mid, r2); i >= max(0, l2); i--){ long long curr = calc_dp(i - 1, k - 1); curr += (p[mid].second - p[i].first + 1ll) * (p[mid].second - p[i].first + 1ll); if(curr < dp[mid][k]){ dp[mid][k] = curr; ptr = i; } } if(p[mid].second >= p[mid + 1].first){ dp[mid][k] -= (p[mid].second - p[mid + 1].first + 1ll) * (p[mid].second - p[mid + 1].first + 1ll); } solve(l, mid - 1, l2, ptr, k); solve(mid + 1, r, ptr, r2, k); } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { for(int i = 0; i < n; i++){ if(r[i] > c[i]){ swap(r[i], c[i]); } p[i].first = r[i]; p[i].second = c[i]; } sort(p, p + n, cmp); int mx = -1, j = 0; for(int i = 0; i < n; i++){ if(p[i].second <= mx){ continue; } //cout << p[i].first << " p[i] " << p[i].second << endl; mx = p[i].second; p[j] = p[i]; j++; } n = j; p[n].first = inf; for(int i = 0; i < n; i++){ dp[i][0] = inf; } for(int i = 1; i <= k; i++){ solve(0, n - 1, 0, n - 1, i); } return dp[n - 1][k]; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 */
#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...