Submission #402766

#TimeUsernameProblemLanguageResultExecution timeMemory
402766danielcm585Aliens (IOI16_aliens)C++14
12 / 100
2 ms332 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define fi first #define se second typedef long long ll; typedef pair<ll,ll> ii; const int N = 1e5; const ll INF = 1e18; int sz; ll dp[N+2], bt[N+2]; vector<int> r, c; struct line { ll m, c; line(ll x, ll y): m(x), c(y) {} bool operator == (line v) { return m == v.m && c == v.c; } ll operator () (ll x) { return m*x+c; } }; struct convexHull { vector<line> v; vector<int> id; bool greater(ll a, ll b, ll c, ll d) { if (a/b != c/d) return a/b > c/d; return (a%b)*d >= (c%d)*b; } bool bad(line a, line b, line c, int x, int y) { if (b == c) return bt[x] > bt[y]; return greater(b.c-a.c,a.m-b.m,c.c-b.c,b.m-c.m); } void insert(line x, int y) { int sz = v.size(); while (sz >= 2 && bad(v[sz-2],v[sz-1],x,id[sz-1],y)) { v.pop_back(); sz--; id.pop_back(); } v.push_back(x); id.push_back(y); } ii query(ll x) { ii ret = ii(INF,INF); for (int l = 0, r = v.size()-1; l <= r; ) { int mid = (l+r)/2; if (v[mid](x) < ret.fi || v[mid](x) == ret.fi && bt[id[mid]] < ret.se) ret = ii(v[mid](x),bt[id[mid]]); if (mid+1 <= r && v[mid+1](x) < v[mid](x)) l = mid+1; else r = mid-1; } return ret; } }; ll sqr(ll a) { return a*a; } int monge(ll mid) { convexHull ch; for (int i = 1; i <= sz; i++) { ch.insert(line(-2*(r[i]-1),dp[i-1]+sqr(r[i]-1)),i-1); ii opt = ch.query(c[i]); dp[i] = opt.fi+sqr(c[i])+mid; bt[i] = opt.se+1; // cout << dp[i] << ' '; } // cout << '\n'; return bt[sz]; } ll take_photos(int n, int m, int k, vector<int> R, vector<int> C) { vector<ii> tmp; for (int i = 0; i < n; i++) { if (R[i] > C[i]) swap(R[i],C[i]); tmp.push_back(ii(R[i],C[i])); } sort(tmp.begin(),tmp.end()); r.push_back(-1); c.push_back(-1); for (auto i : tmp) { while (r.back() == i.fi) { r.pop_back(); c.pop_back(); } r.push_back(i.fi); c.push_back(i.se); } sz = r.size()-1; ll cost = -1, ans; for (ll l = 0, r = (ll)m*m; l <= r; ) { ll mid = (l+r)/2; if (monge(mid) <= k) { ans = dp[sz], cost = mid; r = mid-1; } else l = mid+1; } return ans-cost*k; } /* 5 7 2 0 3 4 4 4 6 4 5 4 6 2 6 2 1 4 4 1 */

Compilation message (stderr)

aliens.cpp: In member function 'ii convexHull::query(ll)':
aliens.cpp:60:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   60 |             if (v[mid](x) < ret.fi || v[mid](x) == ret.fi && bt[id[mid]] < ret.se) ret = ii(v[mid](x),bt[id[mid]]);
      |                                                           ^
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:109:21: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  109 |     return ans-cost*k;
      |                     ^
#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...