| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1291931 | LmaoLmao | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define name "a"
#define int long long
using namespace std;
using ii = pair<int,long long>;
using aa = array<int,3>;
using ll = long long;
const int N=1e6+5;
const int MOD=1e9+7;
int rmq[20][N];
ii dp[N];
int a[N];
int b[N];
int m,n;
int get(int l,int r) {
int x=__lg(r-l+1);
return max(rmq[x][l],rmq[x][r-(1<<x)+1]);
}
vector<ii> v;
bool cmp(aa a,aa b,int cur) {
if(a[0]*cur+a[1]!=b[0]*cur+b[1]) {
return a[0]*cur+a[1]<b[0]*cur+b[1];
} else
return a[2]<b[2];
}
void alien(int delta) {
deque<aa> q;
q.push_back({v[1].fi*2,0,0});
for(int i=1;i<v.size();i++) {
while(q.size()>1 && !cmp(q[0],q[1],v[i].se)) {
q.pop_front();
}
dp[i].fi=q[0][0]*v[i].se+q[0][1]+v[i].se*v[i].se;
dp[i].se=q[0][2]+1;
if(i<v.size()-1) {
aa cur={v[i+1].fi*2,dp[i].fi+v[i+1].fi*v[i+1].fi+delta,dp[i].se};
q.push_back(cur);
//cout << cur[0] << ' ' << cur[1] << endl;
}
//cout << dp[i].fi << endl;
}
return;
}
int take_photos(int M, int N, int k, vector<int> R, vector<int> C) {
m=M;
n=N;
for(int i=0;i<m;i++) {
int x=R[i+1],y=C[i+1];
if(x<y) {
a[y]=max(a[y],y-x+1);
}
else {
a[x]=max(a[x],x-y+1);
}
}
int tmp=-1e18;
for(int i=n;i>0;i--) {
if(a[i]-i<=tmp) a[i]=0;
tmp=max(tmp,a[i]-i);
b[i]=a[i];
}
v.push_back({0,0});
for(int i=1;i<=n;i++) {
if(a[i]) v.push_back({a[i]-i,i});
}
int l=0,r=n*n;
int ans=0;
while(l<=r) {
int mid = l + r >> 1;
alien(mid);
if(dp[v.size()-1].se<=k) {
ans=mid;
r=mid-1;
}
else {
l=mid+1;
}
}
int skibidi=0;
for(int i=1;i<v.size();i++) {
if(v[i].se-a[v[i].se]<v[i-1].se) {
int tmp=v[i-1].se-(v[i].se-a[v[i].se]);
skibidi+=tmp*tmp;
}
}
alien(ans);
if(ans==0) {
cout << dp[v.size()-1].fi-skibidi;
}
else {
cout << dp[v.size()-1].fi+ans*k-skibidi;
}
return 0;
}