Submission #755906

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
755906	2023-06-10T17:35:17 Z	Lib	Aliens (IOI16_aliens)	C++14	Compilation error	0 ms	0 KB

aliens

#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
*/

Compilation message

/usr/bin/ld: /tmp/ccUA8DhQ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccJQujmO.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccUA8DhQ.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status