oj.uz

Submission #237302

# Submission time Handle Problem Language Result Execution time Memory
237302 2020-06-05T18:59:03 Z Mamedov Watching (JOI13_watching) C++14
100 / 100
 291 ms 8696 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back

using namespace std;

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

Compilation message

watching.cpp: In function 'int solve()':
watching.cpp:51:14: warning: 'w' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int mid, w;
              ^

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 5 ms 640 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 59 ms 1296 KB Output is correct
9 Correct 67 ms 3712 KB Output is correct
10 Correct 80 ms 8696 KB Output is correct
11 Correct 30 ms 1144 KB Output is correct
12 Correct 291 ms 8184 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 424 KB Output is correct
15 Correct 5 ms 384 KB Output is correct