| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 755906 | Lib | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct seg{
int s;
int e;
};
bool operator<(const seg &x, const seg &y){
if(x.e!=y.e){
return x.e<y.e;
}else{
return x.s<y.s;
}
}
seg val[100003];
int main(){
int n,m,cnt;
long long ans=10000000000000;
cin>>n>>m>>cnt;
long long dp[n+3][cnt+3];
for(int i=0;i<=cnt;i++){
for(int k=1;k<=cnt;k++){
dp[i][k]=10000000000000;
}
}
int a,b;
for(int i=1;i<=n;i++){
cin>>a>>b;
dp[i][0]=0;
if(a>b){
swap(a,b);
}
b+=1;
val[i]={a,b};
}
val[0]={0,0};
dp[0][0]=0;
sort(val+1,val+n+1);
long long nslen;
long long olen;
dp[1][1]=(val[1].e-val[1].s)*(val[1].e-val[1].s);
for(int i=1;i<=n;i++){
dp[i][1]=(val[i].e-val[1].s)*(val[i].e-val[1].s);
for(int k=2;k<=min(cnt,i);k++){
for(int l=1;l<i;l++){
nslen=val[i].e-val[l+1].s;
olen=min(0,val[l+1].s-val[l].e);
dp[i][k]=min(dp[i][k],dp[l][k-1]+nslen*nslen-olen*olen);
}
}
}
for(int i=1;i<=cnt;i++){
if(dp[n][i]>0){
ans=min(ans,dp[n][i]);
}
}
cout<<ans;
for(int i=1;i<=n;i++){
for(int k=0;k<=cnt;k++){
// cout<<dp[i][k]<<" ";
}
//cout<<val[i].s<<" "<<val[i].e;
// cout<<"\n";
}
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
dp[i][k]: nuot cac doan trong khoang tu 1...i bang dung k doan lon
de nuot tiep diem i bang k doan, phai chon 1 diem l (1<=l<i) bang k-1 doan
*/