#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")
using namespace std;
using namespace __gnu_pbds;
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)
using lll = __int128;
using ll = long long;
using ld = long double;
const int N = 2000 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;
auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;
__int128 read()
{
__int128 x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
void print(__int128 x)
{
if (x < 0)
{
putchar('-');
x = -x;
}
if (x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
bool cmp(__int128 x, __int128 y) { return x > y; }
int n, p, q;
int dp[N][N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.in", "r", stdin);
#endif
cin >> n >> p >> q;
vi a(n);
for (auto &u : a)
cin >> u;
sort(all(a));
p = min(n, p), q = min(n, q);
auto cam = [&](int i, int w) -> int {
int ret = 1;
int st = a[i];
for (int j = i + 1; j < n; ++j)
{
if (a[j] - st + 1 <= w)
++ret;
else
break;
}
return ret;
};
auto check = [&](int mid) -> bool {
for (int i = 0; i <= n; ++i)
memset(dp[i], 0, sizeof dp[i]);
inc(i, 0, p)
{
inc(j, 0, q)
{
if (i + 1 <= p)
dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + cam(dp[i][j], mid));
if (j + 1 <= q)
dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + cam(dp[i][j], 2 * mid));
}
}
inc(i, 0, p) inc(j, 0, q) if (dp[i][j] >= n) return 1;
return 0;
};
int ans = 1e9, lo = 1, hi = 1e9;
while (lo <= hi)
{
int mid = (lo + hi) >> 1;
if (check(mid))
ans = mid, hi = mid - 1;
else
lo = mid + 1;
}
cout << ans;
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:88:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
88 | freopen("in.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
