oj.uz

답안 #261092

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261092 2020-08-11T11:29:39 Z srj 구경하기 (JOI13_watching) C++14
100 / 100
 715 ms 31992 KB 
#include<bits/stdc++.h>
// #include<gondola.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;

//for debugging 
/*
g++ -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -std=c++14 
*/
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// debugging ends here

typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 1e8;
const int mxn = 2005;
const int mxp  = 1e5+1;
ll cache[mxn][mxn];

ll p,q;
ll a[mxn];
ll n;

ll dp(ll i, ll pres, ll w) {
	//cerr << "i=" << i << "; pres=" << pres << endl;
	// caso base
	if (i >= n) return 0LL;
	
	// caso dp
	if (cache[i][pres]!=-1) return cache[i][pres];
	// caso recursivo
	else {
		ll res1 = INF, res2 = INF;
		
		// tomo un p
		ll j=i;
		while (j+1<n && a[j+1]-a[i]+1<=w) j++;
		if (pres) res1 = dp(j+1, pres-1, w);
		
		while (j+1<n && a[j+1]-a[i]+1<=2*w) j++;
		res2 = dp(j+1, pres, w) + 1LL;
		
		return cache[i][pres] = min(res1, res2);
	}
}

int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("bbreeds.in","r",stdin);
	// freopen("bbreeds.out","w",stdout);
	// #endif
	// ll n;
	cin >> n >> p >> q;
	// ll a[n];
	// dbg(n);
	for(ll i =0;i<n;i++)
		cin >> a[i];
	sort(a,a+n);

	if (p+q>=n) {
		cout << 1 << endl;
		exit(0);
	}

	ll lo = 1,hi = 1e9;
	while(lo<=hi){
		ll mid  = lo + (hi-lo)/2;
		// cout << mid << endl; 
		memset(cache,-1,sizeof(cache));
		ll check = dp(0,p,mid);
		// cout << lo << endl;
		// cout << mid << " " << cache[n-1][p] << endl;
		if(check<=q)
			hi = mid-1;
		else lo = mid+1;
	}
	cout << lo << endl;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 135 ms 31744 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 139 ms 31864 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 139 ms 31832 KB Output is correct
8 Correct 140 ms 31744 KB Output is correct
9 Correct 148 ms 31744 KB Output is correct
10 Correct 135 ms 31840 KB Output is correct
11 Correct 143 ms 31744 KB Output is correct
12 Correct 140 ms 31864 KB Output is correct
13 Correct 137 ms 31744 KB Output is correct
14 Correct 136 ms 31836 KB Output is correct
15 Correct 134 ms 31744 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 31864 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 143 ms 31864 KB Output is correct
8 Correct 205 ms 31864 KB Output is correct
9 Correct 359 ms 31992 KB Output is correct
10 Correct 715 ms 31864 KB Output is correct
11 Correct 222 ms 31992 KB Output is correct
12 Correct 653 ms 31992 KB Output is correct
13 Correct 143 ms 31864 KB Output is correct
14 Correct 137 ms 31776 KB Output is correct
15 Correct 139 ms 31864 KB Output is correct