oj.uz

Submission #35037

# Submission time Handle Problem Language Result Execution time Memory
35037 2017-11-17T14:19:40 Z UncleGrandpa925 Watching (JOI13_watching) C++14
100 / 100
 303 ms 33584 KB 
/*input
3 1 1
2
11
17
*/
#include <bits/stdc++.h>
using namespace std;
#define sp ' '
#define endl '\n'
#define fi first
#define se second
#define mp make_pair
#define int long long
#define N 2005
#define bit(x,y) ((x>>y)&1LL)
#define na(x) (#x) << ":" << x
ostream& operator << (ostream &os, vector<int>&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << sp;
	return os;
}
ostream& operator << (ostream &os, pair<int, int> x) {
	cout << x.fi << sp << x.se << sp;
	return os;
}
ostream& operator << (ostream &os, vector<pair<int, int> >&x) {
	for (int i = 0; i < x.size(); i++) os << x[i] << endl;
	return os;
}

int n, P, Q;
vector<int> a;
vector<pair<int, int> > nxt;
int dp[N][N];

bool check(int lim) {
	nxt.clear(); memset(dp, -1, sizeof(dp));
	for (int i = 0; i < a.size(); i++) {
		auto it = upper_bound(a.begin(), a.end(), a[i] + lim - 1);
		it--;
		pair<int, int> ret = mp(0, 0); ret.fi = it - a.begin();
		it = upper_bound(a.begin(), a.end(), a[i] + 2 * lim - 1);
		it--;
		ret.se = it - a.begin();
		nxt.push_back(ret);
	}
	for (int i = 0; i <= P; i++) {
		for (int j = 0; j <= Q; j++) {
			if (dp[i][j] == a.size() - 1) return true;
			if (i != P) {
				dp[i + 1][j] = max(dp[i + 1][j], nxt[dp[i][j] + 1].fi);
			}
			if (j != Q) {
				dp[i][j + 1] = max(dp[i][j + 1], nxt[dp[i][j] + 1].se);
			}
		}
	}
	return false;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> P >> Q;
	a.resize(n);
	for (auto &t : a) cin >> t;
	sort(a.begin(), a.end());
	a.resize(distance(a.begin(), unique(a.begin(), a.end())));
	P = min(P, n); Q = min(Q, n);
	int l = 1, r = 1e9;
	while (l != r) {
		int mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
}

Compilation message

watching.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<long long int>&)':
watching.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << sp;
                    ^
watching.cpp: In function 'std::ostream& operator<<(std::ostream&, std::vector<std::pair<long long int, long long int> >&)':
watching.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < x.size(); i++) os << x[i] << endl;
                    ^
watching.cpp: In function 'bool check(long long int)':
watching.cpp:38:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < a.size(); i++) {
                    ^
watching.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (dp[i][j] == a.size() - 1) return true;
                 ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 33584 KB Output is correct
2 Correct 239 ms 33584 KB Output is correct
3 Correct 219 ms 33584 KB Output is correct
4 Correct 229 ms 33584 KB Output is correct
5 Correct 219 ms 33584 KB Output is correct
6 Correct 216 ms 33584 KB Output is correct
7 Correct 233 ms 33584 KB Output is correct
8 Correct 213 ms 33584 KB Output is correct
9 Correct 206 ms 33584 KB Output is correct
10 Correct 213 ms 33584 KB Output is correct
11 Correct 243 ms 33584 KB Output is correct
12 Correct 223 ms 33584 KB Output is correct
13 Correct 226 ms 33584 KB Output is correct
14 Correct 209 ms 33584 KB Output is correct
15 Correct 209 ms 33584 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 223 ms 33584 KB Output is correct
2 Correct 199 ms 33584 KB Output is correct
3 Correct 256 ms 33584 KB Output is correct
4 Correct 233 ms 33584 KB Output is correct
5 Correct 223 ms 33584 KB Output is correct
6 Correct 229 ms 33584 KB Output is correct
7 Correct 239 ms 33584 KB Output is correct
8 Correct 239 ms 33584 KB Output is correct
9 Correct 239 ms 33584 KB Output is correct
10 Correct 256 ms 33584 KB Output is correct
11 Correct 236 ms 33584 KB Output is correct
12 Correct 303 ms 33584 KB Output is correct
13 Correct 236 ms 33584 KB Output is correct
14 Correct 226 ms 33584 KB Output is correct
15 Correct 243 ms 33584 KB Output is correct