oj.uz

Submission #164962

# Submission time Handle Problem Language Result Execution time Memory
164962 2019-11-24T13:30:49 Z kostia244 Watching (JOI13_watching) C++17
100 / 100
 626 ms 38452 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vvi = vector<vi>;
using pi = pair<ll, ll>;
const ll mod = 7 * 17 * (1 << 23) + 1;
const ll inf = 1e18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll n, p, q, dp[2200][2200];
vi a;
bool can(ll w) {
	memset(dp, 63, sizeof dp);
	dp[0][0] = 0;
	int x = 0, y = 0;
	for(int i = 0; i < n; i++) {
		while(x<n&&a[x]-a[i]+1<=w) x++;
		while(y<n&&a[y]-a[i]+1<=2*w) y++;
		for(int j = 0; j < n; j++) {
			dp[x][j+1] = min(dp[x][j+1], dp[i][j]);
			dp[y][j] = min(dp[y][j], dp[i][j]+1);
		}
	}
	for(int i = 0; i <= p; i++)
		if(dp[n][i]<=q) return true;
	return false;
}
int main() { //DINIC ORZ
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> p >> q;
	a.resize(n);
	for(auto &i : a) cin >> i;
	sort(all(a));
	ll ans = 0;
	for(ll x = 1<<29; x; x>>=1)
		if(!can(ans+x)) ans+=x;
	cout << ans+1;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 38392 KB Output is correct
2 Correct 234 ms 38392 KB Output is correct
3 Correct 245 ms 38284 KB Output is correct
4 Correct 231 ms 38392 KB Output is correct
5 Correct 239 ms 38264 KB Output is correct
6 Correct 255 ms 38392 KB Output is correct
7 Correct 240 ms 38264 KB Output is correct
8 Correct 235 ms 38264 KB Output is correct
9 Correct 241 ms 38328 KB Output is correct
10 Correct 237 ms 38264 KB Output is correct
11 Correct 236 ms 38392 KB Output is correct
12 Correct 239 ms 38392 KB Output is correct
13 Correct 237 ms 38264 KB Output is correct
14 Correct 247 ms 38392 KB Output is correct
15 Correct 253 ms 38396 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 38304 KB Output is correct
2 Correct 243 ms 38364 KB Output is correct
3 Correct 611 ms 38264 KB Output is correct
4 Correct 606 ms 38268 KB Output is correct
5 Correct 608 ms 38452 KB Output is correct
6 Correct 610 ms 38268 KB Output is correct
7 Correct 598 ms 38344 KB Output is correct
8 Correct 601 ms 38264 KB Output is correct
9 Correct 601 ms 38396 KB Output is correct
10 Correct 608 ms 38268 KB Output is correct
11 Correct 598 ms 38264 KB Output is correct
12 Correct 596 ms 38308 KB Output is correct
13 Correct 592 ms 38264 KB Output is correct
14 Correct 626 ms 38264 KB Output is correct
15 Correct 607 ms 38392 KB Output is correct