Submission #413270

#TimeUsernameProblemLanguageResultExecution timeMemory
413270ja_kingyAliens (IOI16_aliens)C++14
25 / 100
3 ms460 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> pii; const ll mxN = 1e5, INF = 1e15; vector<int> stk; ll n, m, k, dp[mxN], pho[mxN], bst, l[mxN], r[mxN]; ll sqr(ll x) {return x*x;} struct line {ll m, c, pcnt;}; vector<line> lines; double sect(line a, line b) {return (double)(a.m - b.m) / (b.c - a.c);} const double EPS = 1e-9; ll eval(line l, ll x) {return l.m*x + l.c;} void upd(line l) { while (lines.size() > 1 && sect(l, lines[lines.size()-2]) < sect(l, lines.back())) { lines.pop_back(); } while (lines.size() > 1 && fabs(sect(l, lines[lines.size()-2]) - sect(l, lines.back())) < EPS && l.pcnt <= lines.back().pcnt) { lines.pop_back(); } lines.push_back(l); bst = min(bst, (ll)lines.size()-1); } line qry(ll x) { while (bst < lines.size()-1 && ((eval(lines[bst+1], x) < eval(lines[bst], x)) || (eval(lines[bst+1], x) == eval(lines[bst], x) && lines[bst+1].pcnt <= lines[bst].pcnt))) bst++; return lines[bst]; } bool slv(int cst) { lines.clear(); upd({-2*l[stk[0]], sqr(l[stk[0]]), 0}); for (int i = 0; i < stk.size(); ++i) { ll ri = r[stk[i]]+1; line res = qry(ri); dp[i] = min(cst + sqr(ri) + eval(res, ri), INF); pho[i] = res.pcnt + 1; if (i+1 < stk.size()) upd({-2*l[stk[i+1]], dp[i] - sqr(max(0ll,ri-l[stk[i+1]])) + sqr(l[stk[i+1]]), pho[i]}); } return dp[stk.size()-1] <= INF && pho[stk.size() - 1] <= k; } ll take_photos(int N, int m, int K, vector<int> R, vector<int> C) { n = N; k = K; for (int i = 0; i < n; ++i) { l[i] = min(R[i], C[i]); r[i] = max(R[i], C[i]); } vector<int> order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int a, int b){return r[a] < r[b];}); for (int i: order) { while (stk.size() && l[stk.back()] >= l[i]) stk.pop_back(); stk.push_back(i); } ll lo = 0, hi = (ll)m*m, mid; while (lo != hi) { mid = lo+hi>>1; if (slv(mid)) hi = mid; else lo = mid + 1; } slv(lo); return dp[stk.size()-1] - k*lo; }

Compilation message (stderr)

aliens.cpp: In function 'line qry(ll)':
aliens.cpp:33:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while (bst < lines.size()-1 && ((eval(lines[bst+1], x) < eval(lines[bst], x)) || (eval(lines[bst+1], x) == eval(lines[bst], x) && lines[bst+1].pcnt <= lines[bst].pcnt))) bst++;
      |            ~~~~^~~~~~~~~~~~~~~~
aliens.cpp: In function 'bool slv(int)':
aliens.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < stk.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
aliens.cpp:45:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         if (i+1 < stk.size()) upd({-2*l[stk[i+1]], dp[i] - sqr(max(0ll,ri-l[stk[i+1]])) + sqr(l[stk[i+1]]), pho[i]});
      |             ~~~~^~~~~~~~~~~~
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:66:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         mid = lo+hi>>1;
      |               ~~^~~
#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...