제출 #498301

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498301		s_samchenko	Swimming competition (LMIO18_plaukimo_varzybos)	C++17	100 / 100	415 ms	22712 KiB

plaukimo_varzybos

#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC target ("avx2")
#define ll long long
#define ff first
#define ss second
#define int ll
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb push_back
#define pii pair <int, int>
#define pdd pair <double, double>
#define vi vector <int>
using namespace std;
using namespace __gnu_pbds;
template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
const int inf = 1e15;
const int mod = 1e9+7;
const int N = 2e5+100;

int n, a, b;
vector <int> v;

bool check(int k){
	vector <int> dp(n+100);
	dp[0] = 1;
	
	for (int i = 0, j = 1; i < n; ++i){
		if (i > 1) dp[i] += dp[i-1];
		if (dp[i] <= 0) continue;
 
		j = max(j, i + 1);
		while (j < n && v[j] - v[i] <= k) ++j;
		
		if (i + a <= min(i + b, j)) {
			dp[i+a]++;
			dp[min(i + b, j) + 1]--;
		}
	}
	
	dp[n] += dp[n-1];
	return dp[n] > 0;
}

void solve(){
	cin >> n >> a >> b; v.resize(n);
	for (int i = 0; i < n; ++i) cin >> v[i];
	sort(all(v));
	
	int l = -1, r = 1e9;
	
	for (; r - l > 1; ){
		int m = (l + r) / 2;
		if (check(m)) r = m;
		else l = m;
	}
	
	cout << r;
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int tt = 1;

	while (tt--){
		solve();
		cout << '\n';
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40