oj.uz

Submission #63562

# Submission time Handle Problem Language Result Execution time Memory
63562 2018-08-02T07:06:28 Z yu0524 Watching (JOI13_watching) C++14
100 / 100
 412 ms 16588 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
using namespace std;
typedef long long ll;
int N, p, q, a, dp[2001][2001];
vector<ll> arr;

int func(ll w, ll maxx = 0, int cur = 0, int sw = p) {
	if (cur >= arr.size()) return 0;
	if (maxx > arr[cur]) return func(w, maxx, cur + 1, sw);
	if (arr.size() - cur <= sw) return 0;

	if (dp[cur][sw] != -1) return dp[cur][sw];

	dp[cur][sw] = func(w, arr[cur] + 2*w, cur+1, sw) + 1;
	if (sw) dp[cur][sw] = min(dp[cur][sw], func(w, arr[cur] + w, cur + 1, sw - 1));
	return dp[cur][sw];
}

int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N;
	cin >> p >> q;

	if (p + q >= N) {
		cout << 1; return 0;
	}

	for (int i = 0; i < N; ++i) {
		cin >> a;
		arr.push_back(a);
	}
	sort(arr.begin(), arr.end());
	arr.resize(distance(arr.begin(), unique(arr.begin(), arr.end())));
	
	ll x = 1, y = 1000000000, mid, res;

	while (x <= y) {
		memset(dp, -1, sizeof(dp));
		mid = (x + y) >> 1;
		
		if (func(mid) <= q) {
			y = mid - 1;
			res = mid;
		}
		else {
			x = mid + 1;
		}
	}

	cout << res;
}

Compilation message

watching.cpp: In function 'int func(ll, ll, int, int)':
watching.cpp:12:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (cur >= arr.size()) return 0;
      ~~~~^~~~~~~~~~~~~
watching.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (arr.size() - cur <= sw) return 0;
      ~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 15992 KB Output is correct
2 Correct 3 ms 15992 KB Output is correct
3 Correct 48 ms 16160 KB Output is correct
4 Correct 3 ms 16160 KB Output is correct
5 Correct 3 ms 16160 KB Output is correct
6 Correct 3 ms 16160 KB Output is correct
7 Correct 51 ms 16320 KB Output is correct
8 Correct 73 ms 16320 KB Output is correct
9 Correct 67 ms 16320 KB Output is correct
10 Correct 88 ms 16376 KB Output is correct
11 Correct 60 ms 16376 KB Output is correct
12 Correct 68 ms 16376 KB Output is correct
13 Correct 50 ms 16376 KB Output is correct
14 Correct 47 ms 16376 KB Output is correct
15 Correct 50 ms 16440 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 16440 KB Output is correct
2 Correct 2 ms 16440 KB Output is correct
3 Correct 2 ms 16440 KB Output is correct
4 Correct 4 ms 16440 KB Output is correct
5 Correct 3 ms 16440 KB Output is correct
6 Correct 2 ms 16440 KB Output is correct
7 Correct 75 ms 16440 KB Output is correct
8 Correct 145 ms 16440 KB Output is correct
9 Correct 324 ms 16508 KB Output is correct
10 Correct 181 ms 16588 KB Output is correct
11 Correct 203 ms 16588 KB Output is correct
12 Correct 412 ms 16588 KB Output is correct
13 Correct 138 ms 16588 KB Output is correct
14 Correct 68 ms 16588 KB Output is correct
15 Correct 76 ms 16588 KB Output is correct