Submission #116104

#	Time	Username	Problem	Language	Result	Execution time	Memory
116104		Just_Solve_The_Problem	Watching (JOI13_watching)	C++11	100 / 100	283 ms	16356 KiB

watching

#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 (stderr)

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 / 50
• Subtask 2: 50 / 50