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 "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int MN=5000+10;
long long inf;
long long dp[MN][MN];
pair<int,int> p[MN];
long long sq(long long x){
return x*x;
}
int a[MN],b[MN];
int po,po1;
double cross(int i,int j){
return 1.0*(a[i]-a[j])/(b[j]-b[i]);
}
int cht[MN];
void add(int i){
while(po>=2 && cross(i,cht[po-2])<cross(cht[po-1],cht[po-2])){
po--;
}
cht[po++]=i;
}
long long ans1(int x,int i){
return 1ll*a[i]*x+b[i];
}
long long ans(int x){
while(po1+1<po && ans1(x,cht[po1+1])<ans1(x,cht[po1])){
po1++;
}
return ans1(x,po1);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
inf=sq(m);
for(int i=0;i<n;i++){
p[i]={min(r[i],c[i]),-max(r[i],c[i])-1};
}
sort(p,p+n);
int n1=unique(p,p+n)-p;
n=0;
int mx=-1;
for(int i=0;i<n1;i++){
if(mx<-p[i].second){
p[n]={p[i].first,-p[i].second};
mx=p[n].second;
n++;
}
}
for(int i=0;i<n;i++){
a[i]=-2*p[i].first;
if(i!=0){
dp[i][0]=inf;
}
b[i]=dp[i][0]+sq(p[i].first);
}
for(int j=1;j<=k;j++){
po=0,po1=0;
add(0);
for(int i=1;i<=n;i++){
dp[i][j]=sq(p[i-1].second)+ans(p[i-1].second);
if(i<n){
b[i]=dp[i][j-1]+sq(p[i].first);
add(i);
dp[i][j]-=sq(max(0,p[i-1].second-p[i].first));
}
}
}
return dp[n][k];
}
# | 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... |