Submission #1228414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228414		thesen	Watching (JOI13_watching)	C++20	100 / 100	118 ms	7992 KiB

watching

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vint vector <int>
#define vll vector <ll>
#define vbool vector<bool>
#define pairint pair<int,int>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;

bool func(ll &n, vll &a, ll &x, ll &y, ll r){
    vector<vll> dp(x+1, vll(y+1));

    for(int i = 1; i <= x; i++){
        for(int k = dp[i-1][0]+1; k <= n; k++){
            if(a[k] - a[dp[i-1][0]+1] < r){
                dp[i][0] = k;
            }else{
                break;
            }
        }
    } if(dp[x][0] == n) return true;
    for(int i = 1; i <= y; i++){
        for(int k = dp[0][i-1]+1; k <= n; k++){
            if(a[k] - a[dp[0][i-1]+1] < r*2){
                dp[0][i] = k;
            }else{
                break;
            }
        }
    } if(dp[0][y] == n) return true;

    ll mx;
    for(int i = 1; i <= x; i++){
        for(int j = 1; j <= y; j++){
            for(int k = dp[i-1][j]+1; k <= n; k++){
                if(a[k] - a[dp[i-1][j]+1] < r){
                    mx = k;
                }else{
                    break;
                }
            } dp[i][j] = mx;
            for(int k = dp[i][j-1]+1; k <= n; k++){
                if(a[k] - a[dp[i][j-1]+1] < r*2){
                    mx = k;
                }else{
                    break;
                }
            } dp[i][j] = max(dp[i][j], mx);
            if(dp[i][j] == n) return true;
        }
    }return false;
}

void solve(ll tc){
    ll n, x, y; cin >> n >> x >> y;
    vll a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    } sort(a.begin(), a.end());

    if(x+y >= n){
        cout << 1 << endl; return;
    }

    ll l = 1, r = a[n], mid;
    bool ans;
    while(l < r){
        mid = (l+r)/2;
        ans = func(n, a, x, y, mid);
        if(ans){
            r = mid;
        }else{
            l = mid;
        }

        if((l+r)/2 == mid){
            if(func(n, a, x, y, l)){
                r = l;
            } break;
        }
    }
    cout << r << endl;
}

int main(){
    ll t; t = 1;
    for(int i = 1; i <= t; i++){
        solve(i);
    }
}

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