oj.uz

답안 #975917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
975917 2024-05-06T03:19:43 Z vjudge1 구경하기 (JOI13_watching) C++17
0 / 100
 1000 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define v(a) vector<a>
#define all(x) x.begin(), x.end()
#define trace2(x,y) cout<<"> "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl
#define trace3(x,y,z) cout<<"> "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl
v(v(ll)) dp;
v(ll) arr;
ll n, p, q; 
ll trav(ll idx, ll cur, ll k){
    if(idx >= n) return 1;
    if(cur < 0) return 1e9;
    if(dp[idx][cur] != -1) return dp[idx][cur];
    ll nextP = upper_bound(arr.begin()+idx+1, arr.begin()+n+1, arr[idx]+k)-arr.begin();
    ll nextQ = upper_bound(arr.begin()+idx+1, arr.begin()+n+1, arr[idx]+2*k)-arr.begin();
    // trace2(nextP, nextQ);
    // trace2(idx, k);
    ll ret = 1e9;
    ret = min(trav(nextP, cur, k)+1, trav(nextQ, cur-1, k));

    return dp[idx][cur] = ret;
}

ll binsearch(ll l, ll r){
    if(l <= r){
        ll mid = (l+r)/2;
        ll temp = trav(0, q, mid);
        for(int i = 0; i < n; i++){
            dp[i].clear();
            dp[i].assign(q+1, -1);
        }
        if(temp <= p){ 
            return min(mid, binsearch(l, mid-1));
        }
        return binsearch(mid+1, r);
    }
}

int main(){
cin >> n >> p >> q;
arr.resize(n);
for(int i = 0; i < n; i++) cin >> arr[i];
if(p+q >= n) cout << 1 << endl;
else {
    p = min(p, n);
    q = min(q, n);
    dp.resize(n+5);
    for(int i = 0; i < n; i++) dp[i].assign(q+5, -1);
    sort(arr.begin(), arr.end());
    cout << binsearch(1, 1e9);
}
}

Compilation message

watching.cpp: In function 'long long int binsearch(long long int, long long int)':
watching.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
   39 | }
      | ^

Subtask #1
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1058 ms 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1024 ms 604 KB Time limit exceeded
2 Halted 0 ms 0 KB -