제출 #1319341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1319341		khanhphucscratch	Watching (JOI13_watching)	C++20	100 / 100	130 ms	16160 KiB

watching

#include<bits/stdc++.h>
using namespace std;
int a[2005], dp[2005][2005];
bool check(int w, int n, int x, int y)
{
    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;
    int j1 = 1, j2 = 1;
    for(int i = 1; i <= n; i++){
        while(a[j1] <= a[i] - w) j1++;
        while(a[j2] <= a[i] - 2*w) j2++;
        for(int j = 0; j <= n; j++){
            if(j > 0) dp[i][j] = min(dp[i][j], dp[j1-1][j-1]);
            dp[i][j] = min(dp[i][j], dp[j2-1][j] + 1);
        }
    }
    for(int i = 0; i <= x; i++) if(dp[n][i] <= y) return 1;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, x, y; cin>>n>>x>>y;
    for(int i = 1; i <= n; i++) cin>>a[i];
    sort(a+1, a+n+1);
    int l = 1, r = 1e9, ans = -1;
    while(l <= r){
        int mid = (l+r)/2;
        if(check(mid, n, x, y) == 1){ans = mid; r = mid-1;}
        else l = mid+1;
    }
    cout<<ans;
}

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