Submission #952186

#	Time	Username	Problem	Language	Result	Execution time	Memory
952186		SmuggingSpun	Watching (JOI13_watching)	C++14	100 / 100	231 ms	15560 KiB

watching

#include<bits/stdc++.h>
#define taskname "watching"
using namespace std;
const int INF = 1e9;
const int lim = 2e3 + 5;
int a[lim];
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	int n, p, q, ans, low = 1, high = 1e9;
	cin >> n >> p >> q;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	if(p + q >= n){
		return cout << 1, 0;
	}
	sort(a + 1, a + n + 1);
	while(low <= high){
		int mid = (low + high) >> 1;
		vector<vector<int>>dp(n + 1, vector<int>(q + 1, INF));
		for(int i = 0; i <= q; i++){
			dp[0][i] = 0;
		}
		for(int i = 1, lp = 1, lq = 1; i <= n; i++){
			while(a[i] - a[lp] >= mid){
				lp++;
			}
			while(a[i] - a[lq] >= (mid << 1)){
				lq++;
			}
			dp[i][0] = dp[lp - 1][0] + 1;
			for(int j = 1; j <= q; j++){
				dp[i][j] = min(dp[lq - 1][j - 1], dp[lp - 1][j] + 1);
			}
		}
		if(dp[n][q] <= p){
			high = (ans = mid) - 1;
		}
		else{
			low = mid + 1;
		}
	}
	cout << ans;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:10:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |   freopen(taskname".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:46:10: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   46 |  cout << ans;
      |          ^~~

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