제출 #290724

#제출 시각아이디문제언어결과실행 시간메모리
290724SamAndAliens (IOI16_aliens)C++17
60 / 100
2104 ms357104 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define m_p make_pair #define fi first #define se second #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) typedef long long ll; const int N = 100005; const ll INF = 1000000009000000009; struct ban { int l, r; }; bool operator<(const ban& a, const ban& b) { if (a.r < b.r) return true; if (a.r > b.r) return false; return a.l > b.l; } int n, m, k; ban a[N]; int hat(pair<int, int> a, pair<int, int> b) { return max(0, min(a.se, b.se) - max(a.fi, b.fi) + 1); } ll** dp; void rec(int j, int l, int r, int ul, int ur) { if (l > r) return; int m = (l + r) / 2; dp[m][j] = INF; int mini; for (int u = ur; u >= ul; --u) { ll yans; if (u == 1) yans = (a[m].r - a[u].l + 1) * 1LL * (a[m].r - a[u].l + 1); else yans = dp[u - 1][j - 1] + (a[m].r - a[u].l + 1) * 1LL * (a[m].r - a[u].l + 1) - hat(m_p(a[u].l, a[m].r), m_p(a[u - 1].l, a[u - 1].r)) * 1LL * hat(m_p(a[u].l, a[m].r), m_p(a[u - 1].l, a[u - 1].r)); if (yans < dp[m][j]) { dp[m][j] = yans; mini = u; } } rec(j, l, m - 1, ul, mini); rec(j, m + 1, r, mini, ur); } ll solv3() { sort(a + 1, a + n + 1); dp = new ll*[n + 5]; for (int i = 0; i < n + 5; ++i) dp[i] = new ll[k + 5]; for (int i = 1; i <= n; ++i) dp[i][0] = INF; for (int j = 1; j <= k; ++j) { rec(j, 1, n, 1, n); /*for (int j = 1; j <= k; ++j) { dp[i][j] = m * m; for (int u = i; u >= 1; --u) { if (u == 1) { dp[i][j] = min(dp[i][j], (a[i].r - a[u].l + 1) * (a[i].r - a[u].l + 1)); continue; } dp[i][j] = min(dp[i][j], dp[u - 1][j - 1] + (a[i].r - a[u].l + 1) * (a[i].r - a[u].l + 1) - hat(m_p(a[u].l, a[i].r), m_p(a[u - 1].l, a[u - 1].r)) * hat(m_p(a[u].l, a[i].r), m_p(a[u - 1].l, a[u - 1].r))); } }*/ } return dp[n][k]; } int t[N * 10 * 4]; void bil(int tl, int tr, int pos) { t[pos] = N * 10; if (tl == tr) { return; } int m = (tl + tr) / 2; bil(tl, m, pos * 2); bil(m + 1, tr, pos * 2 + 1); } void ubd(int tl, int tr, int x, int y, int pos) { if (tl == tr) { t[pos] = min(t[pos], y); return; } int m = (tl + tr) / 2; if (x <= m) ubd(tl, m, x, y, pos * 2); else ubd(m + 1, tr, x, y, pos * 2 + 1); t[pos] = min(t[pos * 2], t[pos * 2 + 1]); } int qry(int tl, int tr, int l, int r, int pos) { if (l > r) return N * 10; if (tl == l && tr == r) return t[pos]; int m = (tl + tr) / 2; return min(qry(tl, m, l, min(m, r), pos * 2), qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1)); } long long take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c) { n = n_; m = m_; k = k_; for (int i = 1; i <= n; ++i) { a[i].l = r[i - 1]; a[i].r = c[i - 1]; if (a[i].l > a[i].r) swap(a[i].l, a[i].r); ++a[i].l; ++a[i].r; } vector<ban> v; sort(a + 1, a + n + 1); bil(1, m, 1); for (int i = n; i >= 1; --i) { if (!(qry(1, m, a[i].r, m, 1) <= a[i].l)) v.push_back(a[i]); ubd(1, m, a[i].r, a[i].l, 1); } n = sz(v); for (int i = 1; i <= n; ++i) a[i] = v[i - 1]; k = min(k, n); return solv3(); }

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

aliens.cpp: In function 'void rec(int, int, int, int, int)':
aliens.cpp:57:8: warning: 'mini' may be used uninitialized in this function [-Wmaybe-uninitialized]
   57 |     rec(j, l, m - 1, ul, mini);
      |     ~~~^~~~~~~~~~~~~~~~~~~~~~~
#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...