oj.uz

답안 #51436

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
51436 2018-06-18T02:23:43 Z Vinhspm 구경하기 (JOI13_watching) C++14
50 / 100
 1000 ms 38176 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<int, int>
#define fi first
#define se second
#define pb push_back
const int N = 2009;
const int oo = 1e9;
const int mod = 1e9 + 7;
int n, P, Q;
int a[N];
bool check(int x)	{
	vector< vector<bool> > dp[N];
	for(int i = 0; i <= n; ++i) {
		dp[i].resize(P + 5);
		for(int j = 0; j <= P; ++j)	{
			dp[i][j].assign(Q + 5, false);
		}
	}
	// base
	dp[0][P][Q] = true;
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j <= P; ++j)
			for(int t = 0; t <= Q ;++t)	{
					if(j < P) 	{
						int nexpos = a[i] - x + 1;
						int pos = lower_bound(a + 1, a + n + 1, nexpos) - a - 1;
						dp[i][j][t] = dp[pos][j + 1][t];
					}
					if(t < Q && dp[i][j][t] == false)	{
						int nexpos = a[i] - 2*x + 1;
						int pos = lower_bound(a + 1, a + n + 1, nexpos) - a - 1;
						dp[i][j][t] = dp[pos][j][t + 1];
					}
				} 
	for(int j = 0; j <= P; ++j)
			for(int t = 0; t <= Q ;++t)
				if(dp[n][j][t])	
					return true;
	return false;
}
signed main()
{
	//freopen("test.txt", "r", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> P >> Q;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	sort(a + 1, a + n + 1); a[0] = -oo;
	if(P + Q >= n) {
		cout << "1";
		return 0;
	}
	//cout << check(3) << '\n'; return 0;
	int l = 1, r = oo;
	while(r > l + 1)	{
		int mid = (l + r)/ 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	for(int i = l; i <= r; ++i)
		if(check(i))	{
			cout << i; return 0;
		}
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 3 ms 544 KB Output is correct
7 Correct 7 ms 668 KB Output is correct
8 Correct 13 ms 788 KB Output is correct
9 Correct 21 ms 788 KB Output is correct
10 Correct 103 ms 788 KB Output is correct
11 Correct 132 ms 1124 KB Output is correct
12 Correct 296 ms 1124 KB Output is correct
13 Correct 8 ms 1124 KB Output is correct
14 Correct 10 ms 1124 KB Output is correct
15 Correct 13 ms 1124 KB Output is correct

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 1260 KB Output is correct
2 Correct 2 ms 1260 KB Output is correct
3 Correct 2 ms 1260 KB Output is correct
4 Correct 2 ms 1260 KB Output is correct
5 Correct 2 ms 1260 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 809 ms 3128 KB Output is correct
8 Execution timed out 1064 ms 38176 KB Time limit exceeded
9 Halted 0 ms 0 KB -