Submission #289992

#	Time	Username	Problem	Language	Result	Execution time	Memory
289992		BeanZ	Watching (JOI13_watching)	C++14	100 / 100	314 ms	31864 KiB

watching

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl '\n'
const int N = 5e5 + 5;
ll n, p, q;
ll dp[2005][2005], a[2005], bestw[2005], bestw2[2005];
bool chk(ll k){
        for (int i = 1; i <= n; i++){
                ll l = 1, h = i;
                ll w2 = a[i] - 2 * k + 1;
                while (l <= h){
                        ll mid = (l + h) >> 1;
                        if (a[mid] < w2) l = mid + 1;
                        else h = mid - 1;
                }
                bestw2[i] = l;
                l = 1, h = i;
                ll w = a[i] - k + 1;
                while (l <= h){
                        ll mid = (l + h) >> 1;
                        if (a[mid] < w) l = mid + 1;
                        else h = mid - 1;
                }
                bestw[i] = l;
        }
        for (int i = 1; i <= n; i++){
                for (int j = 0; j <= q; j++){
                        dp[i][j] = 1e18;
                        ll l = bestw2[i];
                        if (j > 0) dp[i][j] = min(dp[i][j], dp[l - 1][j - 1]);
                        l = bestw[i];
                        dp[i][j] = min(dp[i][j], dp[l - 1][j] + 1);
                }
        }
        for (int i = 0; i <= q; i++){
                if (dp[n][i] <= p) return 1;
        }
        return 0;
}
int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        if (fopen("simplify.in", "r")){
                freopen("simplify.in", "r", stdin);
                freopen("simplify.out", "w", stdout);
        }
        cin >> n >> p >> q;
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a + 1, a + n + 1);
        if ((p + q) >= n) return cout << 1, 0;
        ll l = 1, h = 1e9;
        while (l <= h){
                ll mid = (l + h) >> 1;
                if (chk(mid)) h = mid - 1;
                else l = mid + 1;
        }
        cout << l;
}
/*
*/

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:47:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   47 |                 freopen("simplify.in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:48:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   48 |                 freopen("simplify.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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