Submission #416419

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416419	2021-06-02T11:18:19 Z	DEQK	Watching (JOI13_watching)	C++17	100 / 100	363 ms	4104 KB

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

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.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	204 KB	Output is correct
10	Correct	1 ms	204 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct
12	Correct	2 ms	204 KB	Output is correct
13	Correct	1 ms	204 KB	Output is correct
14	Correct	1 ms	204 KB	Output is correct
15	Correct	1 ms	204 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	3 ms	204 KB	Output is correct
6	Correct	1 ms	204 KB	Output is correct
7	Correct	2 ms	204 KB	Output is correct
8	Correct	39 ms	692 KB	Output is correct
9	Correct	62 ms	716 KB	Output is correct
10	Correct	96 ms	1136 KB	Output is correct
11	Correct	52 ms	1032 KB	Output is correct
12	Correct	363 ms	4104 KB	Output is correct
13	Correct	2 ms	304 KB	Output is correct
14	Correct	2 ms	332 KB	Output is correct
15	Correct	2 ms	332 KB	Output is correct