Submission #802583

#	Time	Username	Problem	Language	Result	Execution time	Memory
802583		KN200711	Watching (JOI13_watching)	C++14	100 / 100	292 ms	15976 KiB

watching

# include <bits/stdc++.h>
# define ll long long
using namespace std;

int N, P, Q;
vector<int> arr;

int mn[2001][2001];
int edge[2][2001];

bool cek(int a) {
	// set edge nya dulu
	for(int i=0;i<N;i++) {
		int T = arr[i] + a - 1;
		edge[0][i] = upper_bound(arr.begin(), arr.end(), T) - arr.begin();
		T += a;
		edge[1][i] = upper_bound(arr.begin(), arr.end(), T) - arr.begin();
		
	//	if(a == 4) cout<<i<<" "<<edge[0][i]<<" "<<edge[1][i]<<endl;
	}
	
	for(int i=0;i<=N;i++) {
		for(int k=0;k<=P;k++) mn[i][k] = 1e9;
	}
	mn[0][0] = 0;
	for(int i=0;i<N;i++) {
		for(int k=0;k+1<=P;k++) {
			mn[edge[0][i]][k + 1] = min(mn[edge[0][i]][k+1], mn[i][k]);
		}
		for(int k=0;k<=P;k++) {
			mn[edge[1][i]][k] = min(mn[edge[1][i]][k], mn[i][k] + 1);
		}
	}
	for(int c=0;c<=P;c++) {
		if(mn[N][c] <= Q) return 1;
	}
	return 0;
}

int main() {
	scanf("%d %d %d", &N, &P, &Q);
	arr.resize(N);
	for(int i=0;i<N;i++) scanf("%d", &arr[i]);
	sort(arr.begin(), arr.end());
	
	if(P + Q >= N) {
		printf("1\n");
		return 0;
	}
	
	for(int i=0;i<=N;i++) {
		for(int k=0;k<=P;k++) mn[i][k] = 1e9;
	}
//	cout<<cek(4)<<endl;
	int l = 1, r = 1e9, ans = -1;
	while(l <= r) {
		int mid = (l + r) / 2;
		if(cek(mid)) {
			ans = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	printf("%d\n", ans);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d %d %d", &N, &P, &Q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:43:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  for(int i=0;i<N;i++) scanf("%d", &arr[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~

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