제출 #330758

#제출 시각아이디문제언어결과실행 시간메모리
330758IgorIAliens (IOI16_aliens)C++17
컴파일 에러
0 ms0 KiB
#include <bits/stdc++.h> using namespace std; const long long INFLL = 1e18; pair<long long, long long> calc(int n, long long M, vector<int> l, vector<int> r) { vector<long long> dp(n, INFLL); vector<long long> bl(n, INFLL); for (int i = 0; i < n; i++) dp[i] = M + 1ll * (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1; struct line{ long long k, b, id; }; vector<line> convex; int lj = 0; for (int i = 0; i < n; i++) { long long res = 1ll * r[i] * r[i]; long long d = INFLL, used = 0; for (int j = 0; j < convex.size(); j++) { line e = convex[j]; if (e.b + e.k * r[i] < d) { d = e.b + e.k * r[i], used = INFLL; lj = j; } if (e.b + e.k * r[i] == d && bl[e.id] < used) { used = bl[e.id]; lj = j; } if (j > lj + 1) break; } res += d; if (res < dp[i]) dp[i] = res, bl[i] = used + 1; if (i + 1 < n) { long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1); long long k = 2 * (1 - l[i + 1]); line L = {k, b, i}; while (convex.size() >= 2) { line A = convex[convex.size() - 2]; line B = convex[convex.size() - 1]; if (1ll * (B.b - L.b) * (L.k - B.k) > 1ll * (A.b - L.b) * (L.k - B.k)) convex.pop_back(); else break; } convex.push_back(L); } } //cout << M << " " << dp[n - 1] << " " << bl[n - 1] << endl; return {dp[n - 1], bl[n - 1]}; } long long take_photos(int n, int m, int k, vector<int> l, vector<int> r) { vector<int> cv(m); for (int i = 0; i < m; i++) { cv[i] = i + 1; } for (int i = 0; i < n; i++) { int x = min(l[i], r[i]); int y = max(l[i], r[i]); cv[y] = min(cv[y], x); } l.clear(); r.clear(); for (int i = 0; i < m; i++) { if (cv[i] <= i) { while (l.size() && l.back() >= cv[i]) l.pop_back(), r.pop_back(); l.push_back(cv[i]), r.push_back(i); } } n = l.size(); //for (int i = 0; i < l.size(); i++) // cout << l[i] << " " << r[i] << endl; long long L = 0, R = 1ll * m * m + 222; long long ans = INFLL; k = min(k, n); while (L + 1 < R) { long long M = (L + R) / 2; if (calc(n, M, l, r).second >= k) L = M; else R = M; } for (long long d = R - 1; d <= R; d++) { pair<long long, long long> res = calc(n, d, l, r); //cout << res.first << " " << res.second << " " << d << " " << k << endl; if (res.second <= k) ans = min(ans, res.first - 1ll * k * d); } return ans; } void solve(int g, vector<int> &l, vector<int> &r, vector<vector<long long> > &dp, int le_i, int ri_i, int le_p, int ri_p) { if (le_i > ri_i) return; int mid_i = (le_i + ri_i) / 2; int id = le_p; for (int p = le_p; p <= ri_p && p < mid_i; p++) { long long res = dp[p][g - 1]; long long L = l[p], R = r[mid_i - 1], covto = -1; if (p) covto = r[p - 1]; if (covto < L) res += 1ll * (R - L + 1) * (R - L + 1); else res += 1ll * (R - L + 1) * (R - L + 1) - 1ll * (covto - L + 1) * (covto - L + 1); if (res < dp[mid_i][g]) { id = p; dp[mid_i][g] = res; } } solve(g, l, r, dp, le_i, mid_i - 1, le_p, id); solve(g, l, r, dp, mid_i + 1, ri_i, id, ri_p); } long long take_photos2(int n, int m, int k, vector<int> l, vector<int> r) { vector<int> cv(m); for (int i = 0; i < m; i++) { cv[i] = i + 1; } for (int i = 0; i < n; i++) { int x = min(l[i], r[i]); int y = max(l[i], r[i]); cv[y] = min(cv[y], x); } l.clear(); r.clear(); for (int i = 0; i < m; i++) { if (cv[i] <= i) { while (l.size() && l.back() >= cv[i]) l.pop_back(), r.pop_back(); l.push_back(cv[i]), r.push_back(i); } } n = l.size(); const long long INFLL = 1e18; vector<vector<long long> > dp(n + 1, vector<long long>(k + 1, INFLL)); dp[0][0] = 0; for (int g = 1; g <= k; g++) { solve(g, l, r, dp, 1, n, 0, n); } return *min_element(dp[n].begin(), dp[n].end()); } signed main() { freopen("80", "r", stdin); srand(time(NULL)); int n, m, k; cin >> n >> m >> k; while (1) { vector<int> r(n), c(n); for (int i = 0; i < n; i++) { //r[i] = rand() % m; //c[i] = rand() % m; //cout << r[i] << " " << c[i] << endl; cin >> r[i] >> c[i]; } long long a = take_photos(n, m, k, r, c); long long b = take_photos2(n, m, k, r, c); cout << a << endl << b << endl << endl; //if (a != b) return 0; } }

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

aliens.cpp: In function 'std::pair<long long int, long long int> calc(int, long long int, std::vector<int>, std::vector<int>)':
aliens.cpp:22:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<calc(int, long long int, std::vector<int>, std::vector<int>)::line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for (int j = 0; j < convex.size(); j++)
      |                         ~~^~~~~~~~~~~~~~~
aliens.cpp: In function 'int main()':
aliens.cpp:171:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  171 |     freopen("80", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~
/tmp/cchGe3eN.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccxBPcvu.o:aliens.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status