oj.uz

답안 #37757

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
37757 2017-12-28T03:52:38 Z MatheusLealV 구경하기 (JOI13_watching) C++14
100 / 100
 219 ms 18624 KB 
#include <bits/stdc++.h>
#define N 2050
#define f first
#define s second
using namespace std;
typedef pair<int, int> pii;

int n, p, q, v[N], dp[N][N], prox[N][3], A, B;

int prox_(int i, int w)
{
	int ini = i, fim = n, mid, best;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(v[mid] - v[i] + 1 <= w) best = mid, ini = mid + 1;

		else fim = mid - 1;
	}

	return best + 1;
}

bool solve(int w)
{
	for(int i = 1; i <= n; i++) prox[i][1] = prox_(i, w), prox[i][2] = prox_(i, 2*w);

	prox[n + 1][1] = n + 1, prox[n + 1][2] = n + 1;

	for(int i = 0; i <= A; i++)
		for(int j = 0; j <= B; j++) dp[i][j] =1;

	for(int p = 0; p <= A ; p++)
	{
		for(int q = 0; q <= B; q++)
		{
			if(p) dp[p][q] = max(dp[p][q], prox[ dp[p - 1][q] ][1]);

			if(q) dp[p][q] = max(dp[p][q], prox[ dp[p][q - 1] ][2]);
		}
	}

	return dp[A][B] >= n + 1;
}

int32_t main()
{
	ios::sync_with_stdio(false); cin.tie(0);

	cin>>n>>A>>B;

	for(int i = 1; i <= n; i++) cin>>v[i];

	if(A + B >= n)
	{
		cout<<"1\n";

		return 0;
	}

	sort(v + 1, v + n + 1);
	
	int ini = 1, fim = 1e9, mid, best = -1;

	while(fim >= ini)
	{
		mid = (ini + fim)/2;

		if(solve(mid)) best = mid, fim = mid - 1;

		else ini = mid + 1;
	}

	cout<<best<<'\n';
}

Compilation message

watching.cpp: In function 'int prox_(int, int)':
watching.cpp:23:16: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best + 1;
                ^
watching.cpp: In function 'bool solve(int)':
watching.cpp:23:16: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
watching.cpp:12:29: note: 'best' was declared here
  int ini = i, fim = n, mid, best;
                             ^
watching.cpp:23:16: warning: 'best' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return best + 1;
                ^
watching.cpp:12:29: note: 'best' was declared here
  int ini = i, fim = n, mid, best;
                             ^

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 18624 KB Output is correct
2 Correct 0 ms 18624 KB Output is correct
3 Correct 0 ms 18624 KB Output is correct
4 Correct 0 ms 18624 KB Output is correct
5 Correct 0 ms 18624 KB Output is correct
6 Correct 0 ms 18624 KB Output is correct
7 Correct 6 ms 18624 KB Output is correct
8 Correct 23 ms 18624 KB Output is correct
9 Correct 29 ms 18624 KB Output is correct
10 Correct 46 ms 18624 KB Output is correct
11 Correct 39 ms 18624 KB Output is correct
12 Correct 219 ms 18624 KB Output is correct
13 Correct 3 ms 18624 KB Output is correct
14 Correct 3 ms 18624 KB Output is correct
15 Correct 3 ms 18624 KB Output is correct