oj.uz

Submission #116104

# Submission time Handle Problem Language Result Execution time Memory
116104 2019-06-10T15:26:27 Z Just_Solve_The_Problem Watching (JOI13_watching) C++11
100 / 100
 283 ms 16356 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = (int)2000 + 7;
const int mod = (int)1e9 + 7;

int dp[N][N];

int n, p, q;
int a[N];
int x;

int solve(int idx, int ost, int lim) {
	if (idx > n) return 0;
	if (lim > a[idx]) return solve(idx + 1, ost, lim);
	int &res = dp[idx][ost];
	if (res != -1) return res;
	if (ost > n - idx) return 0;
	res = 1e9;
	if (ost > 0)
		res = solve(idx + 1, ost - 1, a[idx] + x);
	res = min(res, solve(idx + 1, ost, a[idx] + x + x) + 1);
	return res;
}

main() {
	scanf("%d %d %d", &n, &p, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	sort(a + 1, a + n + 1);
	if (p + q >= n) {
		cout << 1;
		return 0;
	}
	int l = 1;
	int r = 1e9;
	int ans = 1e9;
	while (l <= r) {
		int mid = (l + r) >> 1;
		memset(dp, -1, sizeof dp);
		x = mid;
		if (solve(1, p, -1) <= q) {
			ans = mid;
			r = mid - 1;
		} else {
			l = mid + 1;
		}
	}
	cout << ans;
}

Compilation message

watching.cpp:27:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
watching.cpp: In function 'int main()':
watching.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &p, &q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16248 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 53 ms 16164 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 65 ms 16128 KB Output is correct
8 Correct 69 ms 16248 KB Output is correct
9 Correct 46 ms 16128 KB Output is correct
10 Correct 50 ms 16128 KB Output is correct
11 Correct 46 ms 16128 KB Output is correct
12 Correct 79 ms 16160 KB Output is correct
13 Correct 56 ms 16128 KB Output is correct
14 Correct 44 ms 16128 KB Output is correct
15 Correct 81 ms 16128 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 16144 KB Output is correct
2 Correct 2 ms 304 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 78 ms 16128 KB Output is correct
8 Correct 152 ms 16128 KB Output is correct
9 Correct 187 ms 16128 KB Output is correct
10 Correct 72 ms 16248 KB Output is correct
11 Correct 123 ms 16356 KB Output is correct
12 Correct 283 ms 16248 KB Output is correct
13 Correct 68 ms 16248 KB Output is correct
14 Correct 58 ms 16128 KB Output is correct
15 Correct 45 ms 16128 KB Output is correct