제출 #392583

#제출 시각아이디문제언어결과실행 시간메모리
392583ivan_tudorAliens (IOI16_aliens)C++14
4 / 100
1 ms208 KiB
#include "aliens.h" #include<bits/stdc++.h> using namespace std; struct CHT{ //TODO struct Line{ long long a, b; int id; long long operator ()(int x) const{ return 1LL * a * x + b; } }; deque<Line> dq; bool IntersectX(Line l1, Line l2, Line l3){ // daca l2 e scoasa ca minim de l1 si l3 return (l2.b - l1.b) * (l2.a - l3.a) <= (l1.a - l2.a) * (l3.b - l2.b); } void AddLine(Line l){ while(dq.size() > 1 && IntersectX(dq.end()[-2], dq.end()[-1], l)) dq.pop_back(); dq.push_back(l); } pair<long long, int> getmin(int x){ while(dq.size() > 1 && dq[0](x) >= dq[1](x)) dq.pop_front(); return {dq[0](x), dq[0].id}; } }; const int N = 100005; struct points{ int l, c; bool operator <(points oth) const{ if(l == oth.l) return c > oth.c; return l < oth.l; } }; points p[N]; long long dp[N], cnt[N]; void makedp(int n, long long lambda){ CHT cht; for(int i = 1; i<=n; i++){ long long extracoef = max(0, p[i - 1].c - p[i].l + 1); cht.AddLine({-2LL * p[i].l, 1LL * dp[i - 1] + 1LL * p[i].l * p[i].l - extracoef * extracoef - 2LL*p[i].l, i-1}); pair<long long, int> dpr = cht.getmin(p[i].c); cnt[i] = cnt[dpr.second] + 1; dp[i] = dpr.first + lambda + 1LL * p[i].c * p[i].c + 2LL*p[i].c + 1; } } long long take_photos(int n, int m, int k, std::vector<int> rows, std::vector<int> columns) { for(int i = 0; i < n; i++){ int l = rows[i], c = columns[i]; l++; c++; if(l > c) swap(l, c); p[i+1] = {l, c}; } sort(p + 1, p + n + 1); int maxc = 0; vector<points> noup; for(int i = 1; i<=n;){ int j = i; while(j <=n && p[j].l == p[i].l) j++; if(p[i].c > maxc){ noup.push_back(p[i]); maxc = p[i].c; } i = j; } n = noup.size(); for(int i = 1; i<=n; i++) p[i] = noup[i - 1]; long long good = 0; for(long long p2 = 1LL<<45; p2>0; p2/=2){ makedp(n, good + p2); if(cnt[n] >= k) good += p2; } makedp(n, good); return dp[n] - cnt[n]* good; }
#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...