Submission #264827

#	Time	Username	Problem	Language	Result	Execution time	Memory
264827		Goolakh	Watching (JOI13_watching)	C++17	100 / 100	199 ms	32120 KiB

watching

// FUCKED UP FUCKED UP FUCKED UP FUCKED UP FUCKED UP
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O2")

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define MP make_pair

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=2e3+10, maxm=1e6+10, lg=10, mod=1e9+7, inf=1e18;

ll n,t1,t2,a[maxn],dp[maxn][maxn],nx1[maxn],nx2[maxn];
bool check(ll d){
	memset(dp,0,sizeof(dp));
	for(int i=0,p1=1,p2=1;i<n;i++){
		while(a[p1]-a[i]+1<=d) p1++;
		while(a[p2]-a[i]+1<=2*d) p2++;
		nx1[i]=p1, nx2[i]=p2;
		//if(d==4) cout<<i<<' '<<nx1[i]<<' '<<nx2[i]<<endl;
	}
	for(int i=0;i<=t1;i++)for(int j=0;j<=t2;j++){
		if(dp[i][j]>=n) return 1;
		dp[i+1][j]=max(dp[i+1][j],nx1[dp[i][j]]);
		dp[i][j+1]=max(dp[i][j+1],nx2[dp[i][j]]);
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin>>n>>t1>>t2;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n); a[n]=inf;
	//check(4);
	ll l=0,r=mod-7,mid;
	while(r-l>1){
		mid=(l+r)/2;
		if(check(mid)) r=mid;
		else           l=mid;
	}
	cout<<r;
	
	return 0;
}
// a denial a denial a denial a denial a denial a denial

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