제출 #624194

#제출 시각아이디문제언어결과실행 시간메모리
624194bruceccccccAliens (IOI16_aliens)C++14
25 / 100
2080 ms173052 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; struct Photo { int x, s; }; struct Line { ll m, c; double intersectX(Line b) { return (b.c - c) / (double) (m - b.m); } }; ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector<int> size(m, 0); for (int i = 0; i < n; i++) { if (r[i] <= c[i]) { size[r[i]] = max(size[r[i]], c[i] - r[i] + 1); } else { size[c[i]] = max(size[c[i]], r[i] - c[i] + 1); } } vector<Photo> photos; vector<ll> add(1), st(1); int prev = 0; for (int i = 0; i < m; i++) { if (size[i] > prev) { prev = size[i]; if (photos.empty() || i >= photos.back().x + photos.back().s) { st.push_back(0); add.push_back(add.back() + 1ll * size[i] * size[i]); } else { ll start = photos.back().x + photos.back().s - i; add.push_back(add.back() + 1ll * size[i] * size[i] - start * start); st.push_back(start * start); } photos.push_back({ i, size[i] }); } prev = max(0, prev - 1); } ll ans = add[photos.size()]; vector<vector<Line>> hulls(k+1); vector<vector<ll>> dp(photos.size(), vector<ll>(k+1)); for (int i = 0; i < photos.size(); i++) { for (int j = k; j >= 1; j--) { auto& d = hulls[j-1]; auto& a = dp[i][j]; ll endPoint = photos[i].x + photos[i].s; if (j > 1 && d.size() > 0) { int l = 0, r = d.size() - 1; while (l < r) { int m = (l + r) / 2; if (endPoint < d[m].intersectX(d[m+1])) r = m; else l = m + 1; } auto val = d[l]; a = val.m * endPoint + val.c + 1ll * endPoint * endPoint - add[i+1]; } else if (j == 1) { ll w = endPoint - photos.front().x; a = w * w - add[i+1]; } // if (i > 0) a = min(a, dp[i-1][j-1]); // cout << i << ' ' << j << ' ' << << endl; if (i == photos.size() - 1 && j == k) { ans += a; break; } auto& q = hulls[j]; Line next = { -2 * photos[i+1].x, 1ll * photos[i+1].x * photos[i+1].x - st[i+2] + add[i+1] + a }; while (q.size() >= 2 && next.intersectX(q[q.size()-2]) < q[q.size()-2].intersectX(q.back())) q.pop_back(); q.push_back(next); } } return ans; }

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

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Photo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0; i < photos.size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~
aliens.cpp:75:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Photo>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |       if (i == photos.size() - 1 && j == k) {
      |           ~~^~~~~~~~~~~~~~~~~~~~
#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...