oj.uz

Submission #817891

# Submission time Handle Problem Language Result Execution time Memory
817891 2023-08-09T19:11:45 Z Isam Watching (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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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