제출 #432052

#제출 시각아이디문제언어결과실행 시간메모리
432052TangentAliens (IOI16_aliens)C++17
25 / 100
2053 ms6860 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) long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vpii intervals; rep(i, n) { if (r[i] > c[i]) { swap(r[i], c[i]); } intervals.emplace_back(r[i], -c[i]); } sort(all(intervals)); vpii merged = {{intervals[0].first, -intervals[0].second}}; ffor(i, 1, intervals.size()) { if (-intervals[i].second > merged.back().second) { merged.emplace_back(intervals[i].first, -intervals[i].second); } } vvll dp(k + 1, vll(merged.size() + 1, 1ll << 62)); dp[0][0] = 0; rep(i, merged.size()) { dp[1][i + 1] = sq(merged[i].second - merged[0].first + 1); } ll res = dp[1].back(); ffor(used, 2, k + 1) { ffor(i, used - 1, merged.size()) { rep(j, i) { dp[used][i + 1] = min(dp[used][i + 1], dp[used - 1][j + 1] + sq(merged[i].second - merged[j + 1].first + 1) - sq(max(0, merged[j].second - merged[j + 1].first + 1))); } } res = min(res, dp[used].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...