제출 #59707

#제출 시각아이디문제언어결과실행 시간메모리
59707KieranHorganAliens (IOI16_aliens)C++17
4 / 100
6 ms748 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define int long long vector<pair<int, int>> intervals; int cost(int i, int l) { int overlap = max(0ll, intervals[l].second-intervals[l+1].first+1); return (intervals[i].second-intervals[l+1].first+1)*(intervals[i].second-intervals[l+1].first+1) - overlap*overlap; } long long take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c) { // r.clear(); // c.clear(); // srand(4); // n = 100; // k = 8; // m = 1000; for(int i = 0; i < n; i++) { // r.push_back(rand()%m); // c.push_back(rand()%m); if(c[i] >= r[i]) intervals.push_back({r[i], -c[i]}); else intervals.push_back({c[i], -r[i]}); } sort(intervals.begin(), intervals.end()); auto interStore = intervals; intervals.clear(); intervals.push_back({-1, -1}); int ma = -1; for(auto p: interStore) { if(-p.second > ma) { ma = -p.second; intervals.push_back({p.first, -p.second}); } } n = intervals.size()-1; k = min(k, n); vector<vector<int>> dp(k+1, vector<int>(n+1, 1ll<<60)); vector<vector<int>> opt(k+1, vector<int>(n+1, 0)); dp[0][0] = 0; for(int j = 1; j <= k; j++) { for(int i = n; i >= j; i--) { for(int l = 0; l <= (i==n?j:opt[j][i+1]); l++) { if(dp[j-1][l] + cost(i, l) < dp[j][i]) { opt[j][i] = l; dp[j][i] = dp[j-1][l] + cost(i, l); } } } } return dp[k][n]; }
#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...