Submission #1327547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1327547		ElayV13	Watching (JOI13_watching)	C++20	50 / 100	289 ms	16092 KiB

watching

//g++ -o sol sol.cpp
//cd C:\Users\Asus-1\OneDrive\Desktop
#include <bits/stdc++.h>
using namespace std;
#define ld long double
//#define int long long
const int INF=1e18;
#define S(a) a.begin(),a.end()
#define pb push_back
#define READ(l,r,a) for(int i=l;i<=r;i++) cin>>a[i]
#define printV(l,r,a) for(int i=l;i<=r;i++) cout<<a[i]<<' ';
#define pii pair <int,int>
#define FOR(i,l,r) for(int i=l;i<=r;i++)
int n,p,q;
vector<int>a;
int dp[2001][2001];
int mxp[2001];
int mxq[2001];
bool ok(int w){
	for(int i=0;i<=2000;i++) for(int j=0;j<=2000;j++) dp[i][j]=0,mxp[i]=-1,mxq[i]=-1;
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			if(a[j]-a[i]+1<=2*w) mxq[i]=j;
			if(a[j]-a[i]+1<=w) mxp[i]=j;
		}
	}
	dp[0][0]=0;
	for(int i=0;i<=p;i++){
		for(int j=0;j<=q;j++){
			int idx=dp[i][j];
			dp[i+1][j]=max({dp[i+1][j],dp[i][j],mxp[idx+1]});
			dp[i][j+1]=max({dp[i][j+1],dp[i][j],mxq[idx+1]});
		}
	}
	//cout<<dp[p][q]<<endl;
	return (dp[p][q]==n);
}
void solve(){
	cin>>n>>p>>q;
	p=min(p,n);
	q=min(q,n);
	a.resize(n+1);
	for(int i=1;i<=n;i++) cin>>a[i];
	sort(S(a));
	int l=1,r=1000000001,w=INF;
	while(l<=r){
		int mid=(l+r)>>1;
		if(ok(mid)){
			w=min(w,mid);
			r=mid-1;
		}		
		else l=mid+1;
	}
	cout<<w<<endl;
}
signed main(){
        ios_base::sync_with_stdio();
        cin.tie(0);
	cout.tie(0);
	int T=1;//cin>>T;
	while(T--) solve();
}

Compilation message (stderr)

watching.cpp:7:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    7 | const int INF=1e18;
      |               ^~~~

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