oj.uz

답안 #208134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208134 2020-03-10T04:58:48 Z YJU 구경하기 (JOI13_watching) C++17
50 / 100
 1000 ms 32052 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){
	memset(DP,0,sizeof(DP));
	DP[0][0]=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);
	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 133 ms 31736 KB Output is correct
2 Correct 134 ms 31736 KB Output is correct
3 Correct 134 ms 31736 KB Output is correct
4 Correct 136 ms 31736 KB Output is correct
5 Correct 134 ms 31864 KB Output is correct
6 Correct 136 ms 31736 KB Output is correct
7 Correct 138 ms 32052 KB Output is correct
8 Correct 135 ms 31736 KB Output is correct
9 Correct 136 ms 31736 KB Output is correct
10 Correct 137 ms 31736 KB Output is correct
11 Correct 132 ms 31864 KB Output is correct
12 Correct 136 ms 31740 KB Output is correct
13 Correct 133 ms 31856 KB Output is correct
14 Correct 137 ms 31736 KB Output is correct
15 Correct 136 ms 31736 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 31864 KB Output is correct
2 Correct 141 ms 31992 KB Output is correct
3 Correct 615 ms 31864 KB Output is correct
4 Correct 267 ms 31864 KB Output is correct
5 Correct 143 ms 31864 KB Output is correct
6 Correct 203 ms 31864 KB Output is correct
7 Correct 137 ms 31992 KB Output is correct
8 Correct 261 ms 31864 KB Output is correct
9 Correct 243 ms 31864 KB Output is correct
10 Correct 276 ms 31992 KB Output is correct
11 Correct 230 ms 31864 KB Output is correct
12 Execution timed out 1066 ms 31992 KB Time limit exceeded
13 Halted 0 ms 0 KB -