제출 #1200908

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1200908		PlayVoltz	구경하기 (JOI13_watching)	C++20	100 / 100	415 ms	25004 KiB

watching

#include <bits/stdc++.h>
using namespace std;

int n;
vector <int> vect;
vector <int> bigc;
vector <int> smallc;
int dp[2000][100001];

int watching(int index, int small, int w){
	if (index>=n){
		return 0;
	}
	if (dp[index][small]!=-1){
		return dp[index][small];
	}
	if (vect[index]+small*w>vect[n-1]){
		return 0;
	}
	if (index==n-1 && small==0){
		return 1;
	}
	int usesmall = INT_MAX, usebig;
	usebig = watching(bigc[index], small, w)+1;
	if (small>0){
		usesmall = watching(smallc[index], small-1, w);
	}
	dp[index][small] = min(usebig, usesmall);
	return dp[index][small];
}

int main(){
	int p, q;
	cin>>n>>p>>q;
	vect.resize(n);
	bigc.resize(n);
	smallc.resize(n);
	for (int i=0; i<n; ++i){
		cin>>vect[i];
	}
	if (p+q>=n){
		cout<<1;
		return 0;
	}
	sort(vect.begin(), vect.end());
	int low = 0, high = vect[n-1], ans;
	while (low+1<high){
		for (int i=0; i<n; ++i){
			for (int j=0; j<=p; ++j){
				dp[i][j] = -1;
			}
		}
		int mid = (low+high)/2;
		for (int i=0; i<n; ++i){
            smallc[i] = lower_bound(vect.begin(), vect.end(), vect[i]+mid)-vect.begin();
    	}
	    for (int i=0; i<n; ++i){
            bigc[i] = lower_bound(vect.begin(), vect.end(), vect[i]+mid+mid)-vect.begin();
	    }
		if (watching(0, p, mid)<=q){
			ans = mid;
			high = mid;
		}
		else{
			low = mid;
		}
	}
	cout<<ans;
}

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