oj.uz

답안 #208135

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208135 2020-03-10T04:59:52 Z YJU 구경하기 (JOI13_watching) C++17
100 / 100
 939 ms 11920 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e3+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,P,Q,x,DP[N][N];
vector<ll> v;

bool b(ll k){
	REP(i,P+1)REP(j,Q+1)DP[i][j]=0;
	REP(i,P+1)REP(j,Q+1){
		DP[i][j+1]=max(DP[i][j+1],(ll)(lwb(v.begin(),v.end(),v[DP[i][j]]+2*k)-v.begin()));
		DP[i+1][j]=max(DP[i+1][j],(ll)(lwb(v.begin(),v.end(),v[DP[i][j]]+1*k)-v.begin()));
		if(DP[i][j]==n)return 1;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>P>>Q;
	P=min(P,n);Q=min(Q,n);
	P=min(P,n-Q);
	REP(i,n)cin>>x,v.pb(x);
	sort(v.begin(),v.end());
	ll l=-1,r=MOD;
	while(r-l>1){
		(b((r+l)/2)?r=(r+l)/2:l=(r+l)/2);
	}
	cout<<r<<"\n";
	return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 760 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 6 ms 504 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 4 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 470 ms 8312 KB Output is correct
4 Correct 130 ms 9336 KB Output is correct
5 Correct 8 ms 376 KB Output is correct
6 Correct 8 ms 376 KB Output is correct
7 Correct 6 ms 504 KB Output is correct
8 Correct 129 ms 1656 KB Output is correct
9 Correct 116 ms 4088 KB Output is correct
10 Correct 153 ms 9392 KB Output is correct
11 Correct 103 ms 1784 KB Output is correct
12 Correct 939 ms 11920 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 6 ms 480 KB Output is correct
15 Correct 6 ms 504 KB Output is correct