Submission #1251856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251856		arda	Watching (JOI13_watching)	C++20	100 / 100	599 ms	31780 KiB

watching

#include <bits/stdc++.h>
#define int long long int
#define ff first
#define ss second
const int MOD = 1000000007;
using namespace std;
const int N = 200005;
void solve(){
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> a;
    for(int i = 0; i < n; i++){
        int b;
        cin >> b;
        a.push_back(b);
    }
    sort(a.begin(), a.end());
    int dp[n+1][n+1];
    x = min(x, n);
    int l = 1, r = 1e9;
    while(l != r){
        int w = (l + r)/2;
        for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) dp[i][j] = -1;
        dp[0][x] = y;
        for(int i = 0; i < n; i++){
            for(int j = 0; j <= x; j++){
                int k = dp[i][j];
                if(k == -1) continue;
                if(j != 0){
                    int p = upper_bound(a.begin(), a.end(), a[i]+w-1) - a.begin();
                    dp[p][j-1] = max(dp[p][j-1], k);
                    // cout << w << " " << i << " " << j << " kısa " << p << endl;
                }
                if(k != 0){
                    int p = upper_bound(a.begin(), a.end(), a[i]+2*w-1) - a.begin();
                    dp[p][j] = max(dp[p][j], k-1);
                    // cout << w << " " << i << " " << j << " uzun " << p << endl;
                }
            }
        }
        int ok = 0;
        for(int j = 0; j < x; j++) if(dp[n][j] != -1) ok = 1;
            // cout << w << " " << ok << endl;
        if(ok) r = w;
        else l = w+1;
    }
    cout << l << endl;
}
int32_t main(){
    int t;
    t = 1;
    while(t--) solve();
}

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