제출 #472936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
472936		Joo	구경하기 (JOI13_watching)	C++17	50 / 100	1083 ms	15940 KiB

watching

#include <bits/stdc++.h>
#define DEBUG false
using namespace std;

const int N = 2e3+10;
int n,P,Q,dp[N][N];

main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> P >> Q;
    vector<int> a(n+1, 0);
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    if(P+Q >= n){
        cout << "1\n";
        return 0;
    }

    int l = 1, r = 1e9, ans = -1, lim = min(P, Q), chk = max(P, Q);
    int code = (P < Q);

    while(l <= r){
        int mid = (l+r)/2;
        for(int i=1; i<=n; i++){
            for(int q=0, j; q<=lim; q++){
                dp[i][q] = 1e9;
                if(q > 0){
                    if(code == 0)
                        j = lower_bound(a.begin()+1, a.end(), a[i]-2*mid+1)-a.begin();
                    else
                        j = lower_bound(a.begin()+1, a.end(), a[i]-mid+1)-a.begin();
                    dp[i][q] = dp[j-1][q-1];
                }
                if(code == 0)
                    j = lower_bound(a.begin()+1, a.end(), a[i]-mid+1)-a.begin();
                else
                    j = lower_bound(a.begin()+1, a.end(), a[i]-2*mid+1)-a.begin();
                dp[i][q] = min(dp[i][q], dp[j-1][q]+1);
            }
        }

        if(dp[n][lim] <= chk){
            ans = mid;
            r = mid-1;
        }else{
            l = mid+1;
        }
    }
    cout << ans << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

watching.cpp:8:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    8 | main(){
      | ^~~~

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