제출 #397165

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
397165		keta_tsimakuridze	Watching (JOI13_watching)	C++14	100 / 100	374 ms	31812 KiB

watching

#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=2e3+5,mod=1e9+7,Inf=1e7;
int t,dp[N][N],a[N],n,p,q;
string s;
bool check(int w){
	//cout<<"++";
	for(int i=1;i<=n;i++){
		int l1 = 0, l2 = 0;
		for(int j=n;j>=0;j--) dp[i][j]=Inf;
		for(int j=i;j>=0;j--) {
			while(a[l1+1]<=a[i]-w) l1++;
			while(a[l2+1]<=a[i]-w*2) l2++;
			if(j)dp[i][j] = min(dp[l1][j-1],dp[i][j]);
			dp[i][j] = min(dp[i][j],dp[l2][j] + 1);
		}
	}
	for(int i=0;i<=min(p,n);i++){
    //	cout<<dp[n][i]<<" ";
		if(dp[n][i] <= q) return 1;
	}
	return 0;
}
 main(){
	// t=1;
	cin>>n>>p>>q;
	for(int i=1;i<=n;i++){
		cin >> a[i];
	}
	sort(a+1,a+n+1);
	int l=1,r=1e9+1,ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	cout<<ans;
}

컴파일 시 표준 에러 (stderr) 메시지

watching.cpp:27:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 |  main(){
      |       ^

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50