Submission #1279337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279337		LmaoLmao	구경하기 (JOI13_watching)	C++20	50 / 100	644 ms	31856 KiB

watching

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;

using ii = pair<int,int>;
using aa = array<int,3>;
const int N = 1e5+5;

int a[N];
int dp[2005][2005];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,p,q;
    cin >> n >> p >> q;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
    }
    sort(a+1,a+1+n);
    int l=1,r=1e9;
    int ans=0;
    while(l<=r) {
        int mid = l + r >> 1;
        dp[0][0]=0;
        bool c=0;
        //cout << mid << endl;
        for(int i=1;i<=n;i++) {
            dp[i][0]=1e9;
        }
        for(int j=1;j<=n;j++) {
            int k=1;
            int huytran=1;
            for(int i=1;i<=n;i++) {
                while(k<=n && a[k]<=a[i]-mid) {
                    k++;
                }
                while(huytran<=n && a[huytran]<=a[i]-mid*2) {
                    huytran++;
                }
                dp[i][j]=1e9;
                dp[i][j]=min({dp[k-1][j-1],dp[huytran-1][j]+1});
                if(i==n && dp[i][j]<=q && j<=p) {
                    c=1;
                    //cout << "anhuytran " << i << ' ' << j << ' ' << dp[i][j] << endl;
                }
                //cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j] << endl;
            }
            //cout << endl;
        }
        //cout << endl;
        if(c) {
            ans=mid;
            r=mid-1;
        }
        else {
            l=mid+1;
        }
    }
    cout << ans;
    return 0;
}

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