Submission #1233322

#TimeUsernameProblemLanguageResultExecution timeMemory
1233322CrabCNHWatching (JOI13_watching)C++20
0 / 100
1094 ms327680 KiB
#include <bits/stdc++.h> #define task "BriantheCrab" #define int long long #define pii pair <int, int> #define fi first #define se second #define szf sizeof #define sz(s) (int)((s).size()) #define all(v) (v).begin(), (v).end() typedef long long ll; typedef unsigned long long ull; typedef long double ld; using namespace std; template <class T> void minimize (T &t, T f) {if (t > f) t = f;} template <class T> void maximize (T &t, T f) {if (t < f) t = f;} const int maxN = 2e3 + 5; const int inf = 1e18 + 7; const int mod = 1e2 + 7; // khong tu code thi khong kha len duoc dau int n, P, Q; int a[maxN]; bool check (int w) { vector <vector <int>> dp (n + 2, vector <int> (P + 2, inf)); for (int i = 0; i <= P; i ++) { dp[0][i] = 0; } int curP = 0, curQ = 0; for (int i = 1; i <= n; i ++) { while (a[i] - a[curP] + 1 > w && curP < i) { curP ++; } while (a[i] - a[curQ] + 1 > w * 2 && curQ < i) { //cout << "cc " << a[i] << ' ' << a[curQ] << '\n'; curQ ++; //cout << a[i] - a[curQ] << ' ' << w * 2 << '\n'; } curP -= ((a[i] - a[curP] + 1 <= w) && (curP >= 1)); curQ -= ((a[i] - a[curQ] + 1 <= 2 * w) && (curQ >= 1)); for (int j = 0; j <= P; j ++) { // cout << "trace " << i << ' ' << curP << ' ' << curQ << '\n'; if (j >= 1) { minimize (dp[i][j], dp[curP][j - 1]); } minimize (dp[i][j], dp[curQ][j] + 1); //cout << i << ' ' << j << ' ' << dp[i][j] << '\n'; //if (j >= 1) cout << "tr " << curP << ' ' << j - 1 << ' ' << dp[curP][j - 1] << '\n'; //cout << "tr " << curQ << ' ' << j << ' ' << dp[curQ][j] + 1 << '\n'; } } for (int i = 0; i <= P; i ++) { //cout << dp[n][i] << '\n'; if (dp[n][i] <= Q) { return true; } } return false; } void solve () { cin >> n >> P >> Q; for (int i = 1; i <= n; i ++) { cin >> a[i]; } sort (a + 1, a + n + 1); int l = 1, r = inf, res = -1; while (true) { if (l > r) { break; } int mid = (l + r) >> 1; if (check (mid)) { res = mid; r = mid - 1; } else { l = mid + 1; } } cout << res; return; } signed main () { cin.tie (nullptr) -> sync_with_stdio (false); if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } int t = 1; //cin >> t; while (t --) { solve (); } return 0; } // thfv

Compilation message (stderr)

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