Submission #1261846

#TimeUsernameProblemLanguageResultExecution timeMemory
1261846tminhWatching (JOI13_watching)C++20
0 / 100
24 ms16196 KiB
#include "bits/stdc++.h" using namespace std; #define task "" #define ll long long #define endl '\n' #define fi first #define se second #define vall(a) (a).begin(), (a).end() #define sze(a) (int)a.size() #define pii pair<int, int> #define pll pair<ll, ll> #define ep emplace_back #define pb push_back #define pf push_front const ll mod = 1e9 + 7; const int N = 2005; const int oo = 1e9; bool START; int n, p, q, a[N]; int dp[N][N]; ll nxtp[N], nxtq[N]; int f(int pos, int need) { if (pos == n + 1) return 0; int &res = dp[pos][need]; if (res != -1) return res; res = oo; int pos_ = nxtq[pos]; if (need < q && pos_ != pos) res = min(res, f(pos_, need + 1)); pos_ = nxtp[pos]; if (pos_ != pos) res = min(res, f(pos_, need) + 1); return res; } bool check(int x) { for (int i = 1; i <= n; ++i) { nxtp[i] = upper_bound(a + 1, a + 1 + n, a[i] + x - 1) - a; nxtq[i] = upper_bound(a + 1, a + 1 + n, a[i] + (x << 1) - 1) - a; } memset(dp, -1, sizeof(dp)); return (f(1, 0) <= p); } int cnp() { ll l = 1, r = oo, ans = oo; while(l <= r) { int mid = (l + r) >> 1; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } return ans; } inline void solve() { cout << cnp(); } inline void input() { cin >> n >> p >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; return solve(); } bool END; int main() { if(fopen(task ".inp", "r")) { freopen(task ".inp", "r", stdin); freopen(task ".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); input(); cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl; cerr << "Memory: " << fabs ((&END - &START)) / 1048576.0 << "MB\n"; return 0; }

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...