제출 #282685

#제출 시각아이디문제언어결과실행 시간메모리
282685theStaticMindAliens (IOI16_aliens)C++14
60 / 100
2079 ms9708 KiB
#include<bits/stdc++.h> #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 using namespace std; #include "aliens.h" int64_t dp[2][1000005]; vector<int> L(1000005); vector<ii> item; int64_t cost(int64_t l, int64_t r){ if(r < l) return 0; return (r - l + 1) * (r - l + 1); } void dnc(int k, int l, int r, int optl, int optr){ if(r < l) return; int mid = (l + r) / 2; int opt = optl; for(int i = optl; i <= optr && i <= mid; i++){ if(dp[k][mid] > dp[k - 1][i] + cost(L[i], item[mid].second) - cost(L[i], item[i].second)){ opt = i; dp[k][mid] = dp[k - 1][i] + cost(L[i], item[mid].second) - cost(L[i], item[i].second); } } dnc(k, l, mid - 1, optl, opt); dnc(k, mid + 1, r, opt, optr); } long long take_photos(int m, int n, int k, std::vector<int> r, std::vector<int> c) { item.pb({0, 0}); for(int i = 0; i < m; i++) item.pb({min(r[i], c[i])+1, max(r[i], c[i])+1}); m++; sort(all(item), [&](ii a, ii b){return a.second < b.second;}); for(int i = 0; i <= m; i++) dp[0][i] = dp[1][i] = 1e18; dp[0][0] = 0; L[m - 1] = n + 1; for(int r = m - 2; r >= 0; r--){ L[r] = min(L[r + 1], item[r + 1].first); } for(int i = 1; i <= k; i++){ dnc(1, 0, m - 1, 0, m - 1); for(int r = 0; r < m; r++) dp[1][r] = min(dp[1][r], dp[0][r]); for(int r = 0; r < m; r++){ swap(dp[0][r], dp[1][r]); dp[1][r] = 1e18; } } return dp[0][m - 1]; }
#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...