Submission #416419

#	Time	Username	Problem	Language	Result	Execution time	Memory
416419		DEQK	Watching (JOI13_watching)	C++17	100 / 100	363 ms	4104 KiB

watching

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 300312;
int n, p, q;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> p >> q;
	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	if(p + q >= n) {
		cout << 1;
		return 0;
	} 
	int l = 0, r = 1e9, re;
	while(r >= l) {
		int m = l + r >> 1;
		int ok = 1;
		vector<vector<int>> dp(p + 1, vector<int> (q + 1));
		for(int i = 0; i <= p; i++) {
			int x = 0;
			for(int j = 0; j <= q; j++) {
				while(x < n && a[x] <= dp[i][j]) x++;
				if(i < p) {
					dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);
					if(x < int(a.size())) {
						dp[i + 1][j] = max(dp[i + 1][j], a[x] + m - 1); 
					} else dp[i + 1][j] = 2e9;
				}
				if(j < q) {
					dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]);
					if(x < int(a.size())) {
						dp[i][j + 1] = max(dp[i][j + 1], a[x] + 2 * m - 1);
					} else dp[i][j + 1] = 2e9;
				}
			}
		}
		ok = (dp[p][q] >= a[n - 1]);
		if(ok) {
			re = m,r = m - 1;
		} else l = m + 1;
	}
	cout << re;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:21:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int m = l + r >> 1;
      |           ~~^~~
watching.cpp:47:10: warning: 're' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |  cout << re;
      |          ^~

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