Submission #211876

#TimeUsernameProblemLanguageResultExecution timeMemory
211876lycAliens (IOI16_aliens)C++14
16 / 100
7 ms512 KiB
#include "aliens.h" #include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<=(b);++i) #define RFOR(i,a,b) for(int i=(a);i>=(b);--i) #define SZ(x) ((int)(x).size()) #define SQ(x) ((long long)(x)*(x)) struct Line { int m; long long c; int u; pair<long long,int> eval(int x) { return make_pair((long long)m*x + c, u); } }; struct ConvexHull { deque<Line> dq; long double intersect(Line a, Line b) { return (long double)(a.c-b.c)/(b.m-a.m); } void add(int m, long long c, int u) { Line l = {m,c,u}; while (!dq.empty() && dq.front().m >= m) dq.pop_front(); while (SZ(dq) > 1 && intersect(l,dq[0]) >= intersect(dq[0],dq[1])) dq.pop_front(); //if (dq.empty() || c < dq.front().c) dq.push_front(l); dq.push_front(l); } pair<long long,int> query(int x) { //while (SZ(dq) > 1 && intersect(dq[SZ(dq)-2],dq.back()) >= x) dq.pop_back(); while (SZ(dq) > 1 && dq[SZ(dq)-2].eval(x) <= dq.back().eval(x)) dq.pop_back(); return dq.back().eval(x); } void dbg() { for (auto& x : dq) cout << x.m << " " << x.c << " :: " << x.u << endl; cout << endl; } }; pair<long long,int> solve(int n, int m, vector<array<int,2>>& p, long long lcost) { pair<long long,int> dp[n+1]; dp[n] = make_pair(0,0); stack<int> stk; stk.push(n); ConvexHull ch; RFOR(i,n-1,0){ while (!stk.empty() && p[stk.top()][1] <= p[i][1]) stk.pop(); long long overlap = (!stk.empty() && p[stk.top()][0] <= p[i][1] ? SQ(p[i][1]+1-p[stk.top()][0]) : 0); ch.add(-2*(p[i][1]+1), dp[stk.top()].first + SQ(p[i][1]+1) - overlap, dp[stk.top()].second); dp[i] = ch.query(p[i][0]); dp[i].first += SQ(p[i][0]) + lcost; dp[i].second += 1; stk.push(i); //dp[j+1].first + SQ(p[j][1]+1) - 2*(p[j][1]+1)*p[i][0] + SQ(p[i][0]) // - SQ(p[j][1]+1-p[j+1][0]) if overlap //cout << overlap << " " << ch.query(p[i][0]).first << " " << SQ(p[i][0]) << endl; //cout << "QUERY " << p[i][0] << endl; //cout << "dp " << i << " :: " << dp[i].first << ' ' << dp[i].second << endl; //ch.dbg(); } return dp[0]; } long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) { vector<array<int,2>> p; FOR(i,0,n-1){ if (r[i] > c[i]) p.push_back(array<int,2>{c[i],r[i]}); else p.push_back(array<int,2>{r[i],c[i]}); } sort(p.begin(),p.end()); p.push_back(array<int,2>{1000005,1000005}); //for(auto&x:p){ // cout<<x[0]<<' '<<x[1]<<endl; //} long long lo = -1, hi = 1e12+10; while (hi-lo > 1) { long long mid = (lo+hi)/2; auto res = solve(n,m,p,mid); //cout << mid << " :: " << res.first << " " << res.second << endl; if (res.second <= k) hi = mid; else lo = mid; } //cout << hi << endl; auto ans = solve(n,m,p,hi); //cout << ans.first << " " << ans.second << endl; return ans.first - k * hi; }
#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...