Submission #416404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
416404	2021-06-02T11:06:56 Z	DEQK	Watching (JOI13_watching)	C++17	50 / 100	1000 ms	4156 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++) {
			for(int j = 0; j <= q; j++) {
				if(i < p) {
					int x = upper_bound(a.begin(), a.end(), dp[i][j]) - a.begin();
					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]);
					int x = upper_bound(a.begin(), a.end(), dp[i][j]) - a.begin();
					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	1 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	1 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	2 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

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	1 ms	332 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	168 ms	720 KB	Output is correct
9	Correct	138 ms	740 KB	Output is correct
10	Correct	215 ms	1128 KB	Output is correct
11	Correct	294 ms	992 KB	Output is correct
12	Execution timed out	1083 ms	4156 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-