Submission #477625

#TimeUsernameProblemLanguageResultExecution timeMemory
477625JovanBAliens (IOI16_aliens)C++17
4 / 100
1 ms332 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; const ll INF = 1000000000000000000LL; const int N = 1000000; struct line{ ll k, n; ll eval(ll x){ return k*x + n; } ld intersect(line g){ return 1.0*(n - g.n)/(g.k - k); } } seg[4*N+5]; ll dp[N+5]; int used[N+5]; ll presek(pair <ll, ll> a, pair <ll, ll> b){ ll h = max(0LL, a.second - b.first + 1); return h*h; } void dodaj(deque <pair <line, int>> &q, pair <line, int> k){ while(q.size() > 1){ line g; int us; tie(g, us) = q.back(); q.pop_back(); ld x1 = q.back().first.intersect(g); ld x2 = g.intersect(k.first); if(x1 < x2){ q.push_back({g, us}); break; } } q.push_back(k); } ll query(deque <pair <line, int>> &q, ll x){ while(q.size() > 1 && q[0].first.eval(x) >= q[1].first.eval(x)) q.pop_front(); return q.front().first.eval(x); } void solve(vector <pair <ll, ll>> &vec, ll pen){ int n = vec.size(); deque <pair <line, int>> q; dodaj(q, {{-2*(vec[0].first - 1), vec[0].first*vec[0].first - 2*vec[0].first}, 0}); for(int i=0; i<n; i++){ dp[i] = 1 + vec[i].second*vec[i].second + query(q, vec[i].second) - pen; used[i] = 1 + q.front().second; dodaj(q, {{-2*(vec[i+1].first - 1), vec[i+1].first*vec[i+1].first - 2*vec[i+1].first - presek(vec[i], vec[i+1]) + dp[i]}, used[i]}); } while(!q.empty()) q.pop_back(); } long long take_photos(int n, int m, int k, std::vector<int> _r, std::vector<int> _c) { vector <pair <int, int>> points; for(int i=0; i<n; i++){ if(_r[i] > _c[i]) swap(_r[i], _c[i]); points.push_back({_r[i] + 1, _c[i] + 1}); } sort(points.begin(), points.end(), [](pair <int, int> a, pair <int, int> b){ if(a.second == b.second) return a.first < b.first; return a.second > b.second; }); vector <pair <ll, ll>> vec; for(auto c : points){ if(vec.empty() || c.first < vec.back().first) vec.push_back(c); } reverse(vec.begin(), vec.end()); solve(vec, 0); n = vec.size(); ll res = dp[n-1]; if(used[n-1] <= k) return res; ll l = -1LL*m*m, r = 1LL*m*m, opt = -1LL*m*m; while(l <= r){ ll mid = (l+r)/2; solve(vec, mid); if(used[n-1] <= k){ l = mid + 1; opt = mid; } else r = mid - 1; } solve(vec, opt); return dp[n-1] + opt*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...