//Problem link:
// Libraries
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; //find_by_order, order_of_key
#include <ext/rope>
using namespace __gnu_cxx;
// Data types
typedef string str;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
// Methods
#define MP make_pair
#define F first
#define S second
#define PB push_back
#define sz(a) (int)(a).size()
// Iterator
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
// Variable names
#define y1 y1___
// Loops
#define FOR(i,a,b) for (int i = (a); i <= (b); ++i)
#define RFOR(i,a,b) for (int i = (a); i >= (b); --i)
// Constant variables
const int MOD = 1000000007; // 998244353
const int INF = 2000000005;
const ll LLINF = 1000000000000000005LL;
const ld PI = acos((ld)-1);
const ld EPS = 1e-9;
void setIO(str name="") {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout << setprecision(15) << fixed;
if (fopen((name + ".INP").c_str(), "r")) {
freopen((name + ".INP").c_str(), "r", stdin);
freopen((name + ".OUT").c_str(), "w", stdout);
}
}
int test = 1;
const int MAXN = 2005;
int n, p, q;
ll arr[MAXN];
//vector<vector<vector<int>>> dp;
vector<vector<vector<int>>> mark;
ll w;
int c = 0;
bool dfs(int i, int p, int q) {
if (p < 0 || q < 0) return false;
if (i > n) return true;
if (mark[i][p][q] == c) return false;
// dp[i][p][q] = 0;
mark[i][p][q] = c;
int j = distance(arr, upper_bound(arr+i+1, arr+n+2, arr[i] + w - 1));
if (dfs(j, p-1, q)) {
return true;
}
j = distance(arr, upper_bound(arr+i+1, arr+n+2, arr[i] + 2*w - 1));
if (dfs(j, p, q-1)) {
return true;
}
return false;
}
void solve() {
cin >> n >> p >> q;
FOR(i, 1, n) {
cin >> arr[i];
}
arr[n+1] = LLINF;
if (p + q >= n) {
cout << 1 << '\n';
}
// dp = vector(n+1, vector(p+1, vector(q+1, 0)));
mark = vector<vector<vector<int>>>(n+1, vector<vector<int>>(p+1, vector<int>(q+1, 0)));
ll l = 0;
ll r = 1000000001;
while (l < r) {
w = l + (r-l)/2;
++c;
if (dfs(1, p, q)) {
r = w;
} else {
l = w + 1;
}
}
cout << l << '\n';
}
int main() {
setIO();
//cin >> test;
while (test--) {
solve();
}
return 0;
}
Compilation message
watching.cpp: In function 'void setIO(str)':
watching.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | freopen((name + ".INP").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen((name + ".OUT").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
