제출 #135685

#제출 시각아이디문제언어결과실행 시간메모리
135685Mahdi_JfriAliens (IOI16_aliens)C++14
4 / 100
10 ms764 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ld long double const int maxn = 1e5 + 20; int l[maxn] , r[maxn] , cnt[maxn] , k , n , par[maxn]; ld a[maxn] , b[maxn] , dp[maxn]; ll t2(int x) { return 1LL * x * x; } vector<int> hull; int pt; ld IS(int i , int j) { return (b[i] - b[j]) / (ld)(a[j] - a[i]); } void add(int i) { a[i] = -2 * l[i + 1]; b[i] = dp[i] + t2(l[i + 1]) - t2(max(0 , r[i] - l[i + 1])); int sz = hull.size(); while(sz > 1 && IS(hull[sz - 2] , hull[sz - 1]) >= IS(hull[sz - 1] , i)) { hull.pop_back(); sz--; } hull.pb(i); } ld f(int ind , int x) { return a[ind] * x + b[ind]; } int get(int x) { if(pt >= (int)hull.size()) pt = (int)hull.size() - 1; while(pt + 1 < (int)hull.size() && f(hull[pt] , x) >= f(hull[pt + 1] , x)) pt++; return hull[pt]; } int check(ld x) { memset(cnt , 0 , sizeof cnt); dp[0] = 0; hull.clear(); for(int i = 1; i <= n; i++) { add(i - 1); int ind = get(r[i]); par[i] = ind; dp[i] = f(ind , r[i]) + t2(r[i]) + x; cnt[i] = cnt[ind] + 1; } return cnt[n]; } long long take_photos(int N, int m, int K, vector<int> R, vector<int> C) { m = m; k = K; n = N; vector<pair<int , int> > tmp; for(int i = 0; i < n; i++) { l[i] = min(R[i] , C[i]) , r[i] = max(R[i] , C[i]); tmp.pb({r[i] , -l[i]}); } sort(tmp.begin() , tmp.end()); for(int i = 0; i < n; i++) { l[i] = -tmp[i].second; r[i] = tmp[i].first; } tmp.clear(); int mn = 1e9; for(int i = n - 1; i >= 0; i--) if(mn > l[i]) { mn = l[i]; tmp.pb({l[i] , r[i]}); } reverse(tmp.begin() , tmp.end()); n = tmp.size(); for(int i = 1; i <= n; i++) l[i] = tmp[i - 1].first , r[i] = tmp[i - 1].second + 1; r[0] = l[0] = -1; if(k > n) { check(0); return dp[n]; } ld lx = -1e18 , rx = 1e18; for(int _ = 0; _ < 200; _++) { ld mx = (lx + rx) / 2; int tmp = check(mx); if(tmp == k) { ll tmp = ceil(dp[n] - cnt[n] * mx); return tmp; } if(tmp <= k) rx = mx; else lx = mx; } check(rx); return dp[n] - cnt[n] * rx; }
#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...