oj.uz

Submission #893117

# Submission time Handle Problem Language Result Execution time Memory
893117 2023-12-26T14:25:22 Z mat_jur Watching (JOI13_watching) C++17
100 / 100
 259 ms 15512 KB 
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto &o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
#define ll long long
#define ld long double
#define all(v) (v).begin(), (v).end()
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define ROF(i,r,l) for(int i=(r);i>=(l);--i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

	int n, p, q;
	cin >> n >> p >> q;
	vector<int> a(n);
	REP(i, n) cin >> a[i];
	sort(all(a));
	if (p+q >= n) {cout << 1 << '\n'; return 0;}
	const int inf = 1e9;
	auto ok = [&](int w) {
		vector dp(n+1, vector(p+1, 0));	
		auto bs = [&](int x) {
			int low = -1, high = n;
			while (high-low > 1) {
				int mid = (high+low)/2;
				if (a[mid] >= x) high = mid;
				else low = mid;
			}
			return high;
		};
		FOR(i, 1, n) {
			int p1 = bs(a[i-1]-w+1), p2 = bs(a[i-1]-2*w+1);
			FOR(j, 0, p) {
				dp[i][j] = min(j-1>=0?dp[p1][j-1]:inf, dp[p2][j]+1);
			}
		}
		return dp[n][p] <= q;
	};
	int low = 0, high = int(1e9)+1;
	while (high-low > 1) {
		int mid = (high+low)/2;
		if (ok(mid)) high = mid;
		else low = mid;
	}
	cout << high << '\n';

	return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 1 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 8 ms 484 KB Output is correct
8 Correct 21 ms 1564 KB Output is correct
9 Correct 96 ms 6572 KB Output is correct
10 Correct 259 ms 15512 KB Output is correct
11 Correct 17 ms 1356 KB Output is correct
12 Correct 127 ms 8316 KB Output is correct
13 Correct 8 ms 604 KB Output is correct
14 Correct 8 ms 604 KB Output is correct
15 Correct 8 ms 604 KB Output is correct