Submission #289986

#	Time	Username	Problem	Language	Result	Execution time	Memory
289986		BeanZ	Watching (JOI13_watching)	C++14	50 / 100	1006 ms	20344 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];
bool chk(ll k){
        for (int i = 1; i <= n; i++){
                for (int j = 0; j <= q; j++){
                        dp[i][j] = 1e18;
                        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;
                        }
                        if (j > 0) dp[i][j] = min(dp[i][j], dp[l - 1][j - 1]);
                        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;
                        }
                        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:41:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   41 |                 freopen("simplify.in", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:42:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |                 freopen("simplify.out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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