oj.uz

답안 #516615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516615 2022-01-21T15:36:16 Z Drew_ 구경하기 (JOI13_watching) C++17
100 / 100
 123 ms 17160 KB 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x) cerr << "[" << #x << "]: " << x << "\n";

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using pl = pair<ll, ll>;

constexpr ld PI = 4*atan((ld)1);
constexpr int MAX = 2069;

int n, p, q;
int ar[MAX], small[MAX], big[MAX];
int dp[MAX][MAX];

inline bool check(int w)
{
	for (int i = 1; i <= n; ++i)
	{
		small[i] = big[i] = i;
		while (small[i] < n && ar[small[i] + 1] - ar[i] + 1 <= w) small[i]++;
		while (big[i] < n && ar[big[i] + 1] - ar[i] + 1 <= 2*w) big[i]++;
	}

	memset(dp, 0, sizeof(dp));
	for (int i = 0; i <= min(n, p); ++i)
	{
		for (int j = 0; j <= min(n, q); ++j)
		{
			if (i) dp[i][j] = max(dp[i][j], small[dp[i-1][j] + 1]);
			if (j) dp[i][j] = max(dp[i][j], big[dp[i][j-1] + 1]);
			
			if (dp[i][j] == n)
				return true;
		}
	}

	return false;
}

int main()
{
	fastio;

	cin >> n >> p >> q;
	for (int i = 1; i <= n; ++i)
		cin >> ar[i];
	sort(ar+1, ar+n+1);

	int l = 1, r = 1e9;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << '\n';

	return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 17064 KB Output is correct
2 Correct 58 ms 17036 KB Output is correct
3 Correct 56 ms 17064 KB Output is correct
4 Correct 56 ms 16972 KB Output is correct
5 Correct 65 ms 17068 KB Output is correct
6 Correct 55 ms 16972 KB Output is correct
7 Correct 57 ms 17060 KB Output is correct
8 Correct 55 ms 17084 KB Output is correct
9 Correct 57 ms 17072 KB Output is correct
10 Correct 59 ms 16944 KB Output is correct
11 Correct 58 ms 16972 KB Output is correct
12 Correct 60 ms 17064 KB Output is correct
13 Correct 56 ms 17092 KB Output is correct
14 Correct 58 ms 17060 KB Output is correct
15 Correct 59 ms 17052 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 17100 KB Output is correct
2 Correct 60 ms 16976 KB Output is correct
3 Correct 99 ms 17160 KB Output is correct
4 Correct 82 ms 17100 KB Output is correct
5 Correct 67 ms 17100 KB Output is correct
6 Correct 66 ms 17100 KB Output is correct
7 Correct 79 ms 17100 KB Output is correct
8 Correct 76 ms 17112 KB Output is correct
9 Correct 78 ms 17100 KB Output is correct
10 Correct 92 ms 17104 KB Output is correct
11 Correct 72 ms 17104 KB Output is correct
12 Correct 123 ms 17100 KB Output is correct
13 Correct 83 ms 17096 KB Output is correct
14 Correct 76 ms 17104 KB Output is correct
15 Correct 71 ms 17100 KB Output is correct