Submission #579332

#TimeUsernameProblemLanguageResultExecution timeMemory
579332perchutsAliens (IOI16_aliens)C++17
4 / 100
1 ms300 KiB
#include <bits/stdc++.h> #define all(x) x.begin(), x.end() #define sz(x) (int) x.size() #define endl '\n' #define pb push_back #define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); #define f first #define s second using namespace std; #include "aliens.h" using ll = long long; using ull = unsigned long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; const int inf = 2e9+1; const int mod = 1e9+7; const int maxn = 1e5+100; template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; } template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; } vector<pair<ll,ll>>pareto; bool pode(pair<ll,ll>x,pair<ll,ll>y,pair<ll,ll>z){ return (y.s-x.s)*(z.f-y.f)>=(y.s-z.s)*(x.f-y.f); } pair<ll,ll> solve(ll lambda){ //CHT deque<pair<pair<ll,ll>,ll>>lines; int n = sz(pareto); lines.push_back({{2ll*pareto[0].f,pareto[0].f*pareto[0].f-2ll*pareto[0].f},0});//dummy point // printf("+ %d %d\n",lines.back().f.f,lines.back().f.s); for(int i=0;i<n;++i){ auto [x,y] = pareto[i]; while(sz(lines)>=2&&lines[0].f.f*(-y)+lines[0].f.s>=lines[1].f.f*(-y)+lines[1].f.s){ // printf("- %lld %lld\n",lines.front().f.f,lines.front().f.s); lines.pop_front(); } ll dpi = lines.front().f.f*(-y)+lines.front().f.s + y*y + 1ll + 2ll*y + lambda; ll qnt = lines.front().s + 1ll; if(i!=n-1){ dpi += pareto[i+1].f*pareto[i+1].f - 2*pareto[i+1].f - (max(0ll,y-pareto[i+1].f+1ll))*(max(0ll,y-pareto[i+1].f+1ll)); pair<pair<ll,ll>,ll>atual = {{2*pareto[i+1].f,dpi},qnt}; while(sz(lines)>=2&&pode(atual.f,lines[sz(lines)-2].f,lines.back().f)) lines.pop_back(); lines.pb(atual); // printf("+ %lld %lld\n",lines.back().f.f,lines.back().f.s); }else return {dpi,qnt}; } return {0,0}; } ll take_photos(int n, int m, int k, vector<int> r1, vector<int> c) { vector<ii>v(n); for(int i=0;i<n;++i){ ++r1[i], ++c[i]; if(r1[i]<=c[i])v[i] = {r1[i],c[i]}; else v[i] = {c[i],r1[i]}; } sort(all(v)); for(int i=0;i<n;++i){ if(pareto.empty()||pareto.back().second<v[i].s){ if(!pareto.empty()&&pareto.back().first==v[i].f)pareto.pop_back(); pareto.push_back(v[i]); } } //Lagrange opt. ll l = 0, r = 1e12;//max delta = 1e12 porque m<=1e6, logo lambda <= 1e12 while(l<r){ ll md = (l+r)/2; pair<ll,ll>cur = solve(md); if(cur.s>k)l = md+1ll; else r = md; } pair<ll,ll>res = solve(r); return res.f-res.s*r; } // int main() { // int n, m, k; // assert(3 == scanf("%d %d %d", &n, &m, &k)); // std::vector<int> r(n), c(n); // for (int i = 0; i < n; i++) { // assert(2 == scanf("%d %d", &r[i], &c[i])); // } // long long ans = take_photos(n, m, k, r, c); // printf("%lld\n", ans); // return 0; // }
#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...