Submission #164962

#	Time	Username	Problem	Language	Result	Execution time	Memory
164962		kostia244	Watching (JOI13_watching)	C++17	100 / 100	626 ms	38452 KiB

watching

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