제출 #830036

#제출 시각아이디문제언어결과실행 시간메모리
830036rembocoderAliens (IOI16_aliens)C++17
25 / 100
1 ms468 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; bool cmp(const pair<int, int>& a, const pair<int, int>& b) { if (a.first != b.first) { return a.first < b.first; } return a.second > b.second; } const long long inf = 2e18; long long div_up(long long a, long long b) { if (a < 0) { return a / b; } return (a + b - 1) / b; } long long take_photos(int n, int m, int k, vector<int> x, vector<int> y) { for (int i = 0; i < n; i++) { if (x[i] > y[i]) { swap(x[i], y[i]); } } vector<pair<int, int>> pairs; for (int i = 0; i < n; i++) { pairs.push_back({x[i], y[i]}); } sort(pairs.begin(), pairs.end(), cmp); vector<pair<int, int>> new_pairs; new_pairs.push_back({-1, -1}); int max_y = -1; for (int i = 0; i < n; i++) { if (max_y < pairs[i].second) { max_y = pairs[i].second; new_pairs.push_back(pairs[i]); } } n = new_pairs.size(); vector<long long> l(n), r(n); for (int i = 0; i < n; i++) { l[i] = new_pairs[i].first; r[i] = new_pairs[i].second + 1; } k = min(k, n - 1); auto ans = [&](int lambda) -> pair<long long, int> { vector<pair<long long, int>> dp(n, {inf, -1}); dp[0] = {0, 0}; vector<long long> a(n), b(n); auto count_ab = [&](int i) -> void { a[i] = dp[i].first + l[i + 1] * l[i + 1] - max(0LL, r[i] - l[i + 1]) * max(0LL, r[i] - l[i + 1]); b[i] = 2 * l[i + 1]; }; vector<pair<long long, int>> ch; count_ab(0); ch.push_back({-1, 0}); int ch_from = 0; for (int i = 1; i < n; i++) { while (ch_from + 1 < ch.size() && ch[ch_from + 1].first <= r[i]) { ch_from++; } int from = ch[ch_from].second; dp[i] = {r[i] * r[i] + a[from] - b[from] * r[i] + lambda, dp[from].second + 1}; if (i + 1 == n) { break; } count_ab(i); while (!ch.empty()) { int last = ch.back().second; long long x = ch.back().first; if (a[last] - b[last] * x < a[i] - b[i] * x || a[last] - b[last] * x == a[i] - b[i] * x && dp[last].second < dp[i].second) { break; } ch.pop_back(); } int last = ch.back().second; long long x = div_up(a[i] - a[last], b[i] - b[last]); if (x == ch.back().first) { x++; } ch.push_back({x, i}); if (ch_from >= ch.size()) { ch_from = ch.size() - 1; } } return dp.back(); }; int l_bin = -1, r_bin = m * m; while (r_bin - l_bin > 1) { int mid = (l_bin + r_bin) / 2; if (ans(mid).second <= k) { r_bin = mid; } else { l_bin = mid; } } int lambda = r_bin; pair<long long, int> res = ans(lambda); return res.first - res.second * lambda - (k - res.second) * (lambda - 1); }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In lambda function:
aliens.cpp:65:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             while (ch_from + 1 < ch.size() && ch[ch_from + 1].first <= r[i]) {
      |                    ~~~~~~~~~~~~^~~~~~~~~~~
aliens.cpp:78:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   78 |                     a[last] - b[last] * x == a[i] - b[i] * x && dp[last].second < dp[i].second) {
aliens.cpp:89:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             if (ch_from >= ch.size()) {
      |                 ~~~~~~~~^~~~~~~~~~~~
#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...