Submission #73192

#	Time	Username	Problem	Language	Result	Execution time	Memory
73192		zscoder	구경하기 (JOI13_watching)	C++17	50 / 100	1088 ms	16712 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 

const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

ll a[2001];
int dp[2001][2001];

int n, p, q;


bool can(ll v)
{
	memset(dp, -1, sizeof(dp));
	for(int i = 0; i <= p; i++)
	{
		for(int j = 0; j <= q; j++)
		{
			if(dp[i][j] == n-1) return true;
			dp[i+1][j]=max(dp[i+1][j], int(upper_bound(a, a+n, a[dp[i][j]+1]+v-1) - a - 1));
			dp[i][j+1] = max(dp[i][j+1], int(upper_bound(a,a+n,a[dp[i][j]+1]+2*v-1) - a - 1));
		}
	}
	return false;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> p >> q;
	for(int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	ll ans = -1;
	ll lo = 1; ll hi = ll(1e9);
	ll mid;
	while(lo <= hi)
	{
		mid = (lo+hi)>>1;
		if(can(mid))
		{
			hi = mid - 1;
			ans = mid;
		}
		else
		{
			lo = mid + 1;
		}
	}
	cout << ans;
}

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