| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 224842 | urd05 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<long long,long long> P;
P arr[100000];
P temp[100000];
long long dp[4005]; //dp[i][j] : minimum grid to fill if we should take a picture unitl i-th place with j pictures.
long long now[4005];
const long long INF=1e18;
int n,m,k;
int sz=0;
int ind=0;
struct Line {
long long a,b;
};
struct Fraction {
long long up,down;
};
Fraction cross(Line one,Line two) {
if (one.a<two.a) {
swap(one,two);
}
return {two.b-one.b,one.a-two.a};
}
bool cmp(Fraction one,Fraction two) {
return one.up*two.down<one.down*two.up;
}
Line line[100513];
void insert(Line l) {
if (sz>=1&&line[sz-1].a==l.a) {
if (l.b>line[sz-1].b) {
line[sz-1]=l;
}
return;
}
while (sz>1) {
Fraction before=cross(line[sz-2],line[sz-1]);
Fraction now=cross(line[sz-1],l);
if (cmp(before,now)) {
break;
}
sz--;
}
line[sz++]=l;
}
void getans() {
sz=0;
ind=0;
for(int i=0;i<n;i++) {
if (i>0&&dp[i-1]<=100000000000000LL) {
long long minus=0;
if (i>0&&arr[i-1].second-arr[i].first+2>0) {
minus=(arr[i-1].second-arr[i].first+2)*(arr[i-1].second-arr[i].first+2);
}
insert({-2*arr[i].first,arr[i].first*arr[i].first-4*arr[i].first-minus+dp[i-1]*4});
}
while (ind+1<sz&&cmp(cross(line[ind],line[ind+1]),{arr[i].second,1})) {
ind++;
}
long long val;
if (ind>=sz) {
val=INF;
}
else {
val=line[ind].a*arr[i].second+line[ind].b+(arr[i].second+2)*(arr[i].second+2);
}
if (val%4!=0) {
printf("Error\n");
}
if (val<INF)
val/=4;
now[i]=val;
}
}
bool comp(P a,P b) {
if (a.second==b.second) {
return a.first<b.first;
}
return a.second<b.second;
}
long long take_photos(int nn,int mm,int kk,vector<int> r,vector<int> c) {
n=nn;
m=mm;
k=kk;
for(int i=0;i<n;i++) {
if (r[i]>c[i]) {
swap(r[i],c[i]);
}
temp[i]=P(2*r[i]+1,2*c[i]+1);
}
sort(temp,temp+n,comp);
int s=0;
long long mini=1e8;
for(int i=n-1;i>=0;i--) {
if (temp[i].first<mini) {
arr[s++]=temp[i];
}
mini=min(mini,temp[i].first);
}
n=s;
reverse(arr,arr+n);
for(int i=0;i<n;i++) {
dp[i]=(-2*arr[0].first*arr[i].second+arr[0].first*arr[0].first-4*arr[0].first+(arr[i].second+2)*(arr[i].second+2))/4;
}
long long ret=dp[n-1];
for(int i=2;i<=k;i++) {
getans();
for(int j=0;j<n;j++) {
dp[j]=now[j];
}
ret=min(ret,dp[n-1]);
}
return ret;
}