제출 #838959

#제출 시각아이디문제언어결과실행 시간메모리
838959ballbattleAliens (IOI16_aliens)C++14
100 / 100
1488 ms340872 KiB
#include "aliens.h" #include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; typedef long double f; typedef pair<ll,ll> pll; typedef pair<f,ll> pfl; typedef vector<ll> vll; typedef vector<pll> vpll; typedef vector<pfl> vp; typedef vector<int> vi; struct line { f c; f slope; pfl operator()(ll x) {return make_pair(c + ((f)x)*slope, my_k);} ll my_k; }; typedef vector<line* > vl; #define rep(a,b,c) for(ll a = b; a < c; a++) #define pb(a) push_back(a) #define mp(a,b) make_pair(a,b) #define all(a) a.begin(),a.end() #define sz(a) a.size() pfl operator+ (pfl a, pfl b) {return mp(a.first+b.first,a.second+b.second);} pfl _dp(f lambda); void insert(line*seg); pfl query(f x); ll n; ll k; vpll p; vll h; vp dp; vl lines; long long take_photos(int N, int M, int K, vi R, vi C) { k = K; p.clear(); rep(i,0,N) {if (R[i] > C[i]) {swap(R[i],C[i]);}} // Flip over diagonal rep(i,0,N) {p.pb(mp(C[i],-R[i]));} sort(all(p)); // Sort in a way that makes worse points come before better points rep(i,0,N) { C[i] = p[i].first; R[i] = -p[i].second; } /*cout << "C[i] R[i]" << endl; rep(i,0,N) {cout << C[i] << " " << R[i] << endl;}*/ // C[i] is in increasing order // R[i] is in decreasing order // The first point is the optimal p.clear(); p.pb(mp(-1,-1)); // thing.... rep(i,0,N) { while ((C[i] >= p[sz(p)-1].first) && (R[i] <= p[sz(p)-1].second)) { // Prune bad points p.pop_back(); } p.pb(mp(C[i],R[i])); // Add points in (x,-y) format to p } /*cout << "points:" << endl; rep(i,0,sz(p)) {cout << p[i].first << " " << p[i].second << endl;}*/ n = sz(p); h.resize(n,0); rep(i,0,n-1) {h[i] = p[i].first - p[i+1].second;} /*cout << "h:" << endl; rep(i,0,n) {cout << h[i] << " ";} cout << endl;*/ /*rep(i,0,10) {cout << _dp(f(i)).first << endl;}*/ ll ans = 1000000000001; f lo = f(0.0); f hi = f(1000000000001); f mid; pfl curr; rep(i,0,64) { mid = (lo)/f(2) + (hi)/f(2); //cout << mid << endl; curr = _dp(mid); //cout << (long double)(curr.first) << " " << curr.second << " " << (long double)(mid) << endl; if (curr.second == min(k,n-1)) { ans = llround(curr.first - mid*curr.second); //cout << llround((long double)(curr.first - mid*curr.second)) << " " << (curr.first - mid*curr.second) << endl; break; } else if (curr.second > min(k,n-1)) { lo = mid; } else { hi = mid; /*ll tmp = round(curr.first - mid*(f(curr.second))); // Hotfix ans = min(tmp, ans);*/ } } if (ans == 1000000000001) {ans = round(curr.first - mid*(f(k)));} // Based solution //if (ans==-1) {ans = round(curr.first - mid*(f(curr.second)));} //cout << n-1 << endl; return ans; } pfl _dp(f lambda) { lines.clear(); dp.clear(); dp.resize(n,mp((f)0,0)); rep(i,0,n) { if (i!=0) dp[i] = mp((f)(p[i].first*p[i].first),0) + query((f)p[i].first) + mp(lambda,1); // wtf based line* new_line = new line; //lines.pb(new line); new_line->my_k = dp[i].second; // include k xd new_line->c = dp[i].first + (f)(p[i].first*p[i].first - 2*p[i].first*(h[i]+1) + ((h[i] < 0) ? (h[i]+1)*(h[i]+1) : 0)); new_line->slope = (f)(-2*(p[i].first-h[i]-1)); insert(new_line); } /*cout << "dp: "; rep(i,0,n) {cout << dp[i].first - lambda*dp[i].second << "," << dp[i].second << " ";} cout << endl; cout << lines.size() << ": "; rep(i,0,lines.size()) {cout << lines[i]->c << "," << lines[i]->slope << "," << lines[i]->my_k << " ";} cout << endl;*/ return dp[n-1]; } pfl query(f x) { // binary search ll lo = 0; ll hi = lines.size()-1; ll mid = (lo+hi)/2; while (lo != hi) { f intersect = (lines[mid]->c - lines[mid+1]->c)/(lines[mid+1]->slope - lines[mid]->slope); if (intersect < x) { // move right lo = mid+1; } else { // move left hi = mid; } mid = (lo+hi)/2; } return (*lines[mid])(x); } void insert(line*seg) { // done while (lines.size() >= 2) { // remove now defunct lines line* curr = lines.back(); f i1 = (curr->c - seg->c)/(seg->slope - curr->slope); line* curr2 = lines[lines.size()-2]; f i2 = (curr2->c - curr->c)/(curr->slope - curr2->slope); if (i1 < i2) {lines.pop_back();} else {break;} } lines.pb(seg); } // Insertsection of two lines // y = x*slope + c // x*s1 + c1 = x*s2 + c2 // x*(s1-s2) = c2-c1 // x = (c2-c1)/(s1-s2);
#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...