Submission #791195

#	Time	Username	Problem	Language	Result	Execution time	Memory
791195		shoryu386	Watching (JOI13_watching)	C++17	100 / 100	220 ms	16092 KiB

watching

#include <bits/stdc++.h>
using namespace std;
#define maxN 2001
int nextSmol[maxN], nextBeeg[maxN];
int dp[maxN][maxN];
int n, small, big;

int recur(int index, int bigCam){ //return number of small cams needed, if we want to cover all from index and onwards with only bigCam number of big cameras
	if (index >= n) return 0;
	if (dp[index][bigCam] != -1) return dp[index][bigCam];
	return dp[index][bigCam] = min(recur(nextSmol[index], bigCam) + 1, bigCam == 0 ? INT_MAX : recur(nextBeeg[index], bigCam-1));
}

int main(){
	cin >> n >> small >> big;
	
	int arr[n];
	for (int x = 0; x < n; x++) cin >> arr[x];
	
	sort(arr, arr+n);
	
	int l = 1, r = arr[n-1] - arr[0] + 1;
	int bestAns = INT_MAX;
	while (l <= r){
		int w = (l+r)/2;
		//time to test if valid
		//we precompute the next arrays
		int next = 0;
		for (int x = 0; x < n; x++){
			while (arr[x] - arr[next] >= w){
				nextSmol[next] = x;
				next++;
			}
		}
		for (int x = next; x < n; x++){
			nextSmol[x] = n; //n signifies the end
		}
		
		next = 0;
		for (int x = 0; x < n; x++){
			while (arr[x] - arr[next] >= 2*w){
				nextBeeg[next] = x;
				next++;
			}
		}
		for (int x = next; x < n; x++){
			nextBeeg[x] = n; //n signifies the end
		}
		
		/*
		if (w == 4){
			for (int x = 0; x < n; x++) cout << nextSmol[x] << ' ';
			cout << '\n';
			
			for (int x = 0; x < n; x++) cout << nextBeeg[x] << ' ';
			cout << '\n';
		}
		*/
		
		
		memset(dp, -1, sizeof(dp));
		int ans = recur(0, min(n, big));
		
		if (ans > small){
			//illegal
			//cout << "ill: " << w << ' ' << ans << '\n';
			l = w+1;
		}
		else{
			//legal
			//cout << "leg: " << w << ' ' << ans << '\n';
			bestAns = w;
			r = w-1;
		}
	}
	cout << bestAns;
	
}

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