제출 #1253328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1253328		cheetah	Watching (JOI13_watching)	C++20	100 / 100	507 ms	30420 KiB

watching

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstdint>
//#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e9+7;
int n;  
vector<int>v,a,b;
vector<vector<int>>dp;
int f(int pos,int q,int w){
	if(q<0)return 2037;
	if(pos>=n)return 0;
	if(dp[pos][q]!=2037)return dp[pos][q];
	dp[pos][q]=min(f(a[pos],q,w)+1,f(b[pos],q-1,w));
	return dp[pos][q];
}

int32_t main(){  
	  
	int p,q;
	cin>>n>>p>>q; 
	v.assign(n,0),a.assign(n,0),b.assign(n,0);
	for(int i=0;i<n;i++)cin>>v[i];
	if(p+q>=n){
		cout<<1;
		return 0;
	}
	
	auto check=[&](int m){
		dp.assign(n,vector<int>(q+1,2037));
		for(int i=0;i<n;i++){
			a[i]=lower_bound(v.begin(),v.end(),v[i]+m)-v.begin();
			b[i]=lower_bound(v.begin(),v.end(),v[i]+2*m)-v.begin();
		}
		return f(0,q,m)<=p;
	};
	sort(v.begin(),v.end());
	int l=1,r=N;
    while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<l<<endl;
}

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50