oj.uz

Submission #1047307

# Submission time Handle Problem Language Result Execution time Memory
1047307 2024-08-07T11:54:50 Z Minbaev Watching (JOI13_watching) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
 
using namespace std;
 
const int inf = 1e9;
 
int32_t main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        
        int n, p, q;
        cin >> n >> p >> q;
 
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) cin >> a[i];
        sort(a.begin() + 1, a.end());
 
        if (p + q >= n) {
                cout << 1 << '\n';
                return 0;
        }
 
        int lf = 0, rg = inf, ans = -1;
        while (lf <= rg) {
                int md = (lf + rg) / 2;
 
                int ok = 0;
                vector<vector<int>> dp(p + 1, vector<int>(q + 1));
                for (int i = 0; i <= p; i++) {
                        for (int j = 0; j <= q; j++) {
                                if (i - 1 >= 0) {
                                        int x = a[dp[i - 1][j] + 1] + md - 1;
                                        int y = upper_bound(a.begin(), a.end(), x) - a.begin() - 1;
                                        dp[i][j] = max(dp[i][j], y);
                                }
 
                                if (j - 1 >= 0) {
                                        int x = a[dp[i][j - 1] + 1] + 2 * md - 1;
                                        int y = upper_bound(a.begin(), a.end(), x) - a.begin() - 1;
                                        dp[i][j] = max(dp[i][j], y);
                                }
 
                        }
                }
                
                if (dp[p][q] == n) {
                        ans = md;
                        rg = md - 1;
                } else {
                        lf = md + 1;
                }
        }
 
        cout << ans << '\n';
        
        return 0;
}

Compilation message

watching.cpp: In function 'int32_t main()':
watching.cpp:31:21: warning: unused variable 'ok' [-Wunused-variable]
   31 |                 int ok = 0;
      |                     ^~

Subtask #1
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 1 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -