제출 #794435

#제출 시각아이디문제언어결과실행 시간메모리
794435prvocisloAliens (IOI16_aliens)C++17
100 / 100
794 ms15400 KiB
#pragma once #include <algorithm> #include <bitset> #include <cassert> #include <chrono> #include <cmath> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <random> #include <set> #include <string> #include <vector> typedef long long ll; typedef long double ld; using namespace std; struct seg { int l, r; }; bool cmp(seg a, seg b) { if (a.l == b.l) return a.r > b.r; return a.l < b.l; } void upd(ll& a, ll b) { a = min(a, b); } ll sq(ll x) { return x * x; } struct line { ld a, b; // a x + b int val; ld eval(ld x) { return a * x + b; } }; ld inter(line a, line b) // prvy moment ked b zacne byt mensia ako a (b ma mensi slope inak) { // b.a * x + b.b < a.a * x + a.b -> x < (a.b - b.b) / (b.a - a.a) if (abs(b.a - a.a) < 1e-9) return -1; return (ld)(a.b - b.b) / (ld)(b.a - a.a); } vector<line> cht; void add(line a) { while (cht.size() >= 2 && inter(cht.end()[-2], cht.end()[-1]) > inter(cht.end()[-2], a)) cht.pop_back(); while (cht.size() >= 1 && inter(cht.end()[-1], a) < 0) cht.pop_back(); cht.push_back(a); } int id = 0; line mini(ld x) { id = max(0, min((int)cht.size() - 2, id)); while (id + 1 < cht.size() && cht[id + 1].eval(x) < cht[id].eval(x)) id++; return cht[id]; } void upd(pair<ld, int>&a, pair<ld, int> b) { a = min(a, b); } pair<ld, int> eval(vector<seg> v, ld price) { cht.clear(), id = 0; int n = v.size(); vector<pair<ld, int> > dp(n); add({ 0, (ld)sq(v.back().r + 1) }); for (int r = 0; r < n; r++) { dp[r] = { sq(v[r].r - v[0].l + 1) + price, 1 }; line l = mini(v[r].r); upd(dp[r], { l.eval(v[r].r) + sq(v[r].r) + price, l.val + 1 }); if (r == n - 1) return dp[r]; line nw; nw.a = -2. * (v[r + 1].l - 1); nw.b = dp[r].first + sq(v[r + 1].l - 1) - sq(max(0, v[r].r - v[r + 1].l + 1)); nw.val = dp[r].second; add(nw); } } long long take_photos(int n, int m, int k, vector<int> l, vector<int> r) { vector<seg> v; for (int i = 0; i < n; i++) { if (r[i] < l[i]) swap(l[i], r[i]); v.push_back({ l[i], r[i] }); } sort(v.begin(), v.end(), cmp); vector<seg> v2; for (seg i : v) if (v2.empty() || v2.back().r < i.r) v2.push_back(i); v = v2; n = v.size(); k = min(k, n); ld lo = 0., hi = sq(m); for (int it = 0; it < 100; it++) { ld mi = (lo + hi) / 2.; if (eval(v, mi).second > k) lo = mi; else hi = mi; } pair<ld, int> p = eval(v, hi); p.first -= (ld)k * hi; return (ll)(p.first + 0.3); }

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

aliens.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens.cpp: In function 'line mini(ld)':
aliens.cpp:60:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  while (id + 1 < cht.size() && cht[id + 1].eval(x) < cht[id].eval(x)) id++;
      |         ~~~~~~~^~~~~~~~~~~~
aliens.cpp: In function 'std::pair<long double, int> eval(std::vector<seg>, ld)':
aliens.cpp:68:29: warning: control reaches end of non-void function [-Wreturn-type]
   68 |  vector<pair<ld, int> > dp(n);
      |                             ^
#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...