oj.uz

답안 #817891

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817891 2023-08-09T19:11:45 Z Isam 구경하기 (JOI13_watching) C++17
100 / 100
 278 ms 8620 KB 
#include<iostream>
#include<algorithm>

using namespace std;

int n, p, q;
const int MAX = 2001;
int dp[MAX][MAX];
int x[MAX];

int Find(int pos, int seg){
    int xpos = x[pos + 1] + seg - 1;
    int l = pos + 1, r = n - 1, mid, last = pos;
    while(l <= r){
            mid = l + ((r - l) >> 1);
            if(x[mid] <= xpos){
                last = mid;
                l = mid + 1;
            }else{
                r = mid - 1;
            }
    }
    return last;
}
bool check(int& w){
    dp[0][0] = -1;
    for(int i = 0; i <= p; ++i){
        for(int j = 0; j <= q; ++j){
                if(!i && !j) continue;
                if(!i) dp[i][j] = Find(dp[i][j-1], (w << 1));
                else if(!j) dp[i][j] = Find(dp[i-1][j], w);
                else dp[i][j] = max(Find(dp[i-1][j], w), Find(dp[i][j-1], (w << 1)));
                if(dp[i][j] == n - 1) return true;
        }
    }
    return false;
}
int solve(){
    cin >> n >> p >> q;
    for(int i = 0; i < n; ++i){
        cin >> x[i];
    }
    if(p + q >= n) return 1;
    sort(x, x + n);
    int l = 1, r = x[n-1], mid, w;
    while(l <= r){
        mid = l + ((r - l) >> 1);
        if(check(mid)){
            w = mid;
            r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    return w;
}
int main(){
    ios_base::sync_with_stdio(false);
    cout << solve() << '\n';
    exit(0);
}

Compilation message

watching.cpp: In function 'int solve()':
watching.cpp:45:33: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
   45 |     int l = 1, r = x[n-1], mid, w;
      |                                 ^

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 42 ms 1108 KB Output is correct
9 Correct 48 ms 3668 KB Output is correct
10 Correct 69 ms 8620 KB Output is correct
11 Correct 24 ms 988 KB Output is correct
12 Correct 278 ms 7936 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct