제출 #812907

#제출 시각아이디문제언어결과실행 시간메모리
812907FatihSolakAliens (IOI16_aliens)C++17
4 / 100
1 ms212 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; struct CHT{ deque<pair<long long,int>> lines; deque<long long> times; deque<int> cnt; long long intersect(pair<long long,int> line1, pair<long long,int> line2){ return (line2.first - line1.first + (line1.second - line2.second - 1)) / (line1.second - line2.second); } void add_line(pair<long long,int> line,int num){ long long opt = 0; while(lines.size()){ opt = max(opt,intersect(lines.back(),line)); if(opt <= times.back()){ lines.pop_back(); times.pop_back(); cnt.pop_back(); } else break; } lines.push_back(line); times.push_back(opt); cnt.push_back(num); } pair<long long,int> get(int x){ while(times.size() > 1 && times[1] <= x){ times.pop_front(); lines.pop_front(); cnt.pop_front(); } return {lines[0].first + (long long) x * lines[0].second,cnt[0]}; } }; long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){ vector<pair<long long,long long>> points; for(int i = 0;i<n;i++){ if(r[i] < c[i]) swap(r[i],c[i]); points.push_back({r[i],c[i]}); } sort(points.begin(),points.end(),[&](pair<int,int> a,pair<int,int> b){ if(a.first == b.first) return a.second > b.second; return a.first < b.first; }); vector<pair<long long,long long>> tmp; for(auto u:points){ while(tmp.size() && tmp.back().second >= u.second){ tmp.pop_back(); } tmp.push_back(u); } points = tmp; // for(auto u:points){ // cerr << u.first << ' ' << u.second << endl; // } n = points.size(); function<pair<int,long long>(long long)> get = [&](long long C){ // cout << C << endl; CHT vals; vector<long long> dp(n+1); vector<int> cnt(n+1); for(int i = 1;i<=n;i++){ long long val = dp[i-1] + points[i-1].second * points[i-1].second - 2*points[i-1].second; if(i > 1) val -= max(0ll,points[i-2].first - points[i-1].second + 1) * max(0ll,points[i-2].first - points[i-1].second + 1); vals.add_line({val,-2*points[i-1].second},cnt[i-1]); auto x = vals.get(points[i-1].first); dp[i] = x.first + points[i-1].first * points[i-1].first + 2 * points[i-1].first + 1 + C; cnt[i] = x.second + 1; // dp[i] = 2e18; // for(int j = 0;j<i;j++){ // long long extra = 0; // if(j > 0) // extra -= max(0ll,points[j-1].first - points[j].second + 1) * max(0ll,points[j-1].first - points[j].second + 1); // // cout << j << ' ' << extra << endl; // long long num = dp[j] + (points[i-1].first - points[j].second + 1) * (points[i-1].first - points[j].second + 1) + extra + C; // if(num < dp[i]){ // dp[i] = num; // cnt[i] = cnt[j] + 1; // } // } // cout << dp[i] << ' ' << cnt[i] << endl; } return make_pair(cnt[n],dp[n] - k * C); }; long long tl = 0,tr = (long long)m * m; while(tl < tr){ long long tm = (tl + tr)/2; if(get(tm).first <= k){ tr = tm; } else tl = tm + 1; } return get(tl).second; }
#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...