제출 #298361

#제출 시각아이디문제언어결과실행 시간메모리
298361zoooma13Aliens (IOI16_aliens)C++14
25 / 100
2089 ms1088 KiB
#include "bits/stdc++.h" #include "aliens.h" using namespace std; bool query = 0; struct line{ long long m ,b; mutable function <const line*()> succ; bool operator<(const line&rhs) const{ if(!query) return m < rhs.m; const line *s = succ(); return s ? (b-s->b) < rhs.m*(s->m-m) : 0; } }; struct hull:multiset<line>{ bool bad(iterator y){ auto z = next(y); if(y == begin()){ if(z == end()) return 0; return (y->m==z->m) && (y->b<=z->b); } auto x = prev(y); if(z == end()) return (y->m==x->m) && (y->b<=x->b); return (1.0)*(x->b-y->b)*(z->m-y->m) >= (1.0)*(y->b-z->b)*(y->m-x->m); } void add(long long m ,long long b){ auto it = insert({-m ,-b}); //remove - for max it -> succ = [=]{ return next(it)==end() ? 0:&*next(it); }; if(bad(it)){ erase(it); return; } while(next(it) != end() && bad(next(it))) erase(next(it)); while(it != begin() && bad(prev(it))) erase(prev(it)); } long long eval(long long x){ if(empty()) return -LLONG_MAX; query = 1; auto l = *lower_bound({x,0}); query = 0; return -(l.m*x+l.b); //remove - for max } }; long long sqr(long long num){ return num*num; } long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) { vector <pair<int ,int>> rngs ,po; for(int i=0; i<n; i++){ if(r[i] < c[i]) swap(r[i] ,c[i]); rngs.push_back({c[i] ,-r[i]}); } sort(rngs.begin() ,rngs.end()); int mx = -1; for(auto&r : rngs) if(-r.second > mx){ po.push_back({r.first ,-r.second+1}); mx = -r.second; } po.insert(po.begin() ,make_pair(-1 ,0)); n = po.size(); vector <long long> dp(n ,1e18) ,exdp(n ,1e18); dp[0] = 0 ,exdp[0] = 0; while(k--){ swap(dp ,exdp); hull h; for(int i=1; i<n; i++){ h.add(-2*po[i].first ,exdp[i-1] + sqr(po[i].first) - sqr(max(0 ,po[i-1].second-po[i].first))); dp[i] = sqr(po[i].second) + h.eval(po[i].second); ///for(int j=0; j<i; j++) /// dp[i] = min(dp[i] ,exdp[j] + sqr(po[i].second-po[j+1].first+1) - sqr(max(0 ,po[j].second-po[j+1].first+1))); } } return dp.back(); }
#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...