Submission #1281703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281703		ducanh0811	Watching (JOI13_watching)	C++20	100 / 100	768 ms	23288 KiB

watching

#include <bits/stdc++.h>
bool M1;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 2005
int n, p, q;
int a[MAXN];
int dp[MAXN][MAXN];

///++++++++++++++++++++++++++++++++++++++///

bool check(int x) {
    FOR(i, 0, p) FOR(j, 0, q) {
        if (i + j > n) break;
        dp[i][j] = 0;
    }
    dp[0][0] = 1;
    FOR(i, 0, p) FOR(j, 0, q) {
        if (i + j > n || dp[i][j] == 0) break;
        if (dp[i][j] == n + 1) return true;
        int &curIndex = dp[i][j];
        int useP = upper_bound(a + 1, a + 1 + n, a[curIndex] + x - 1) - a;
        int useQ = upper_bound(a + 1, a + 1 + n, a[curIndex] + 2 * x - 1) - a;
        dp[i + 1][j] = max(dp[i + 1][j], useP);
        dp[i][j + 1] = max(dp[i][j + 1], useQ);
    }
    return false;
}

void solve() {
    cin >> n >> p >> q;
    FOR(i, 1, n) cin >> a[i];
    sort(a + 1, a + 1 + n);
    int lo = 0, hi = a[n] - a[1] + 5, ans = hi;
    while (lo <= hi) {
        int mid = (lo + hi) >> 1;
        if (check(mid)) {
            ans = mid;
            hi = mid - 1;
        } else lo = mid + 1;
    }
    cout << ans;
}

///++++++++++++++++++++++++++++++++++++++///

#define task "test"
int32_t 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);
    solve();
    bool M2;
    cerr << "++++++++++++++++++++++++++++\n";
    cerr << "Time: " << clock() << "ms" << '\n';
    cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
    cerr << "++++++++++++++++++++++++++++\n";
    return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int32_t main()':
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(task".inp","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(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50