제출 #116418

#제출 시각아이디문제언어결과실행 시간메모리
116418davitmargAliens (IOI16_aliens)C++17
60 / 100
2072 ms358888 KiB
/*DavitMarg*/ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <set> #include <queue> #include <iomanip> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <bitset> #include <ctype.h> #include <fstream> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(),v.end() using namespace std; struct line { LL k, b; line(LL K = 0, LL B = 0) { k = K; b = B; } }; vector<line> convex; bool del(line a,line b,line c) { pair<LL, LL> x1, x2; x1 = MP(c.b - a.b, a.k - c.k); x2 = MP(c.b - b.b, b.k - c.k); //assert(x1.second && x2.second); if (b.k == c.k) return c.b >= b.b; if ((x1.second < 0) == (x2.second < 0)) return x1.first * x2.second > x2.first * x1.second; else return x1.first * x2.second < x2.first * x1.second; } LL getY(LL x,line p) { return x * p.k + p.b; } void build() { convex.clear(); } void add(line p) { while (convex.size() >= 2 && del(convex[convex.size() - 2], convex[convex.size() - 1], p) ) convex.pop_back(); convex.PB(p); } bool check(int pos,LL x) { if (pos + 1 != convex.size() && getY(x, convex[pos + 1]) < getY(x, convex[pos])) return 0; if (pos - 1 >= 0 && getY(x, convex[pos]) < getY(x, convex[pos - 1])) return 0; return 1; } LL get(LL x) { int l, r, m; LL ans = -mod * mod; l = 0; r = convex.size() - 1; while (l <= r) { m = (l + r) / 2; ans = max(ans, getY(x, convex[m])); if (check(m, x)) l = m + 1; else r = m - 1; } return ans; } int n, m, k; vector<pair<int, int>> c; vector<pair<LL, LL>> a,p; vector<vector<LL>> dp; int Main() { for (int i = 0; i < c.size(); i++) { if (c[i].first > c[i].second) swap(c[i].first, c[i].second); p.PB(MP(c[i].first, c[i].second)); } sort(all(p), [](pair<LL, LL> a, pair<LL, LL> b) { if (a.first != b.first) return a.first < b.first; return b.first > a.first; }); a.PB(MP(-1, -1)); for (int i = 0; i < p.size(); i++) if (a.back().second < p[i].second) a.PB(p[i]); n = a.size() - 1; k = min(k, n); dp.resize(k + 5, vector<LL>(n + 5, 0)); for (int i = 1; i <= n; i++) dp[1][i] = (a[i].second - a[1].first + 1) * (a[i].second - a[1].first + 1); for (int i = 2; i <= k; i++) { build(); for (int j = i - 1; j <= i - 1; j++) add(line(2 * (a[j + 1].first - 1), max(a[j].second - a[j + 1].first + 1, 0ll) * max(a[j].second - a[j + 1].first + 1, 0ll) - dp[i - 1][j] - (a[j + 1].first - 1) * (a[j + 1].first - 1))); for (int j = i; j <= n; j++) { dp[i][j] = -get(a[j].second) + a[j].second* a[j].second; if (j != n) add(line(2 * (a[j + 1].first - 1), max(a[j].second - a[j + 1].first + 1, 0ll) * max(a[j].second - a[j + 1].first + 1, 0ll) - dp[i - 1][j] - (a[j + 1].first - 1) * (a[j + 1].first - 1))); } } return 0; } LL take_photos(int N, int M, int K, vector<int> y, vector<int> x) { n = N; m = M; k = K; while (!y.empty()) { c.PB(MP(y.back(),x.back())); y.pop_back(); x.pop_back(); } Main(); return dp[k][n]; } #ifdef death int main() { int N, M, K; vector<int> R, C; cin >> N >> M >> K; for (int i = 0; i < N; i++) { R.PB(0); C.PB(0); cin >> R.back() >> C.back(); } cout << take_photos(N, M, K, R, C) << endl; return 0; } #endif /* 3 4 3 0 1 1 2 2 3 5 6 4 0 1 1 2 2 3 3 4 4 5 2 6 2 1 4 4 1 5 7 2 0 3 4 4 4 6 4 5 4 6 */

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

aliens.cpp: In function 'bool check(int, long long int)':
aliens.cpp:72:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (pos + 1 != convex.size() && getY(x, convex[pos + 1]) < getY(x, convex[pos]))
      ~~~~~~~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'int Main()':
aliens.cpp:104:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < c.size(); i++)
                  ~~^~~~~~~~~~
aliens.cpp:118:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < p.size(); i++)
                  ~~^~~~~~~~~~
#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...