# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
979804 | vjudge1 | Aliens (IOI16_aliens) | C++17 | 207 ms | 7660 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
//#include "game.h"
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
struct deal{
ll x,y,z;
};
long double slope(deal x,deal y){
return ((long double)x.y-y.y)/(y.x-x.x);
}
pll dp[100005];
vector<pll>pt;
pll solve(ll x,int n){
deque<deal>dq;dq.pb({-2*(pt[0].f-1),(pt[0].f-1)*(pt[0].f-1),0});
for(int i=0;i<n;i++){
while(dq.size()>1&&slope(dq[0],dq[1])<pt[i].s)dq.pop_front();
dp[i] = {dq[0].x*pt[i].s+pt[i].s*pt[i].s+dq[0].y+x,dq[0].z+1};
if(i==n-1)continue;deal tmp = {-2*(pt[i+1].f-1),(pt[i+1].f-1)*(pt[i+1].f-1)+dp[i].f-max(1ll*0,pt[i].s-pt[i+1].f+1)*max(1ll*0,pt[i].s-pt[i+1].f+1),dp[i].s};
while(dq.size()>1&&slope(dq[dq.size()-2],dq.back())>slope(dq.back(),tmp))dq.pop_back();
dq.pb(tmp);
}return dp[n-1];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<n;i++){
if(r[i]>c[i])swap(r[i],c[i]);
pt.pb({c[i],-r[i]});
}sort(all(pt));
stack<pll>st;
for(auto it : pt){
while(!st.empty()&&(st.top().s>=-it.s||st.top().f==it.f))st.pop();
st.push({it.f,-it.s});
}n=st.size();while(!pt.empty())pt.pop_back();
while(!st.empty())pt.pb({st.top().s,st.top().f}),st.pop();
reverse(all(pt));ll le=0,re=1e18;
while(le<re){
ll md=(le+re)>>1;
if(solve(md,n).s<=k)re=md;
else le=md+1;
}return solve(le,n).f-le*k;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |