| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 224818 | urd05 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 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 "alines.h"
using namespace std;
typedef pair<int,int> P;
P arr[100000];
P temp[100000];
long long dp[505][1005]; //dp[i][j] : minimum grid to fill if we should take a picture unitl i-th place with j pictures.
long long ans(int ind,int take) {
if (ind==-1) {
return 0;
}
if (take==0) {
return 1e18;
}
if (dp[ind][take]!=-1) {
return dp[ind][take];
}
long long ret=1e18;
for(int i=0;i<=ind;i++) {
long long val=ans(i-1,take-1);
int plus=min({arr[i].first,arr[i].second,arr[ind].first});
int minus=arr[ind].second;
int mid=(plus+minus)/2;
long long len=0;
len=max(len,(long long)(mid>arr[i].first?mid-arr[i].first:arr[i].first-mid));
len=max(len,(long long)(mid>arr[i].second?mid-arr[i].second:arr[i].second-mid));
val+=len*len;
if (i>0) {
if (arr[i-1].second>mid-len) {
val-=(arr[i-1].second-mid+len)*(arr[i-1].second-mid+len);
}
}
ret=min(ret,val);
}
dp[ind][take]=ret;
return ret;
}
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 n,int m,int k,int r[],int c[]) {
memset(dp,-1,sizeof(dp));
for(int i=0;i<n;i++) {
if (r[i]>c[i]) {
swap(r[i],c[i]);
}
temp[i]=P(2*r[i],2*c[i]+2);
}
sort(temp,temp+n,comp);
int sz=0;
int mini=1e8;
for(int i=n-1;i>=0;i--) {
if (temp[i].first<mini) {
arr[sz++]=temp[i];
}
mini=min(mini,temp[i].first);
}
n=sz;
reverse(arr,arr+n);
return ans(n-1,k);
}