제출 #432066

#제출 시각아이디문제언어결과실행 시간메모리
432066TangentAliens (IOI16_aliens)C++17
25 / 100
2084 ms472 KiB
#include "aliens.h" #include "bits/stdc++.h" using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef vector<int> vii; typedef vector<ll> vll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<vii> vvii; typedef vector<vll> vvll; typedef vector<vpii> vvpii; typedef vector<vpll> vvpll; #define ffor(i, a, b) for (ll i = (a); i < (ll)(b); i++) #define fford(i, a, b) for (ll i = (a); i > (ll)(b); i--) #define rep(i, n) ffor(i, 0, n) #define forin(x, a) for (auto &x: a) #define all(a) a.begin(), a.end() #define sq(x) (ll)(x) * (x) pii intervals[100000], merged[100000]; long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { rep(i, n) { if (r[i] > c[i]) { swap(r[i], c[i]); } intervals[i] = {r[i], -c[i]}; } sort(intervals, intervals + n); merged[0] = {intervals[0].first, -intervals[0].second}; int cnt = 1; ffor(i, 1, n) { if (-intervals[i].second > merged[cnt - 1].second) { merged[cnt++] = {intervals[i].first, -intervals[i].second}; } } vll dp(cnt, 1ll << 62); rep(i, cnt) { dp[i] = sq(merged[i].second - merged[0].first + 1); } ll res = dp.back(); ffor(used, 2, k + 1) { vll ndp(cnt, 1ll << 62); int start = cnt - 2; fford(i, cnt - 1, used - 2) { fford(j, start, -1) { ll curr = dp[j] + sq(merged[i].second - merged[j + 1].first + 1) - sq(max(0, merged[j].second - merged[j + 1].first + 1)); if (curr < ndp[i]) { ndp[i] = curr; start = j; } } } dp = move(ndp); res = min(res, dp.back()); } return res; }
#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...