oj.uz

Submission #944445

# Submission time Handle Problem Language Result Execution time Memory
944445 2024-03-12T17:50:43 Z cot Watching (JOI13_watching) C++14
100 / 100
 185 ms 32004 KB 
#include <iostream>
#include <algorithm>
#include <math.h>
#include <set>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define pp pop_back
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define r0 return 0
using namespace std;
const int N = 2005;
int n,m,p,q,a[N],l1,l2,l,r,ans;
set < pii > s;
int dp[N][N];
bool check (int x) {
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) dp[i][j] = 1e9;
        auto it = s.lower_bound({a[i] - x + 1, 0});
        it--; l1 = (*it).ss;
        auto it2 = s.lower_bound({a[i] - 2 * x + 1, 0});
        it2--; l2 = (*it2).ss;
        for (int j = 0; j <= i; j++) {
            // patara kamera
            if (j >= 1) {
                dp[i][j] = dp[l1][j - 1];  
            }
            // didi kamera
            
            dp[i][j] = min(dp[i][j], dp[l2][j] + 1);
            if (i == n and j <= p and dp[i][j] <= q) return 1;
        }
    }
    return 0;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> p >> q;
    s.insert({-1e9, 0});
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        s.insert({a[i], i});
    }
    l = 1; r = 1e9;
    while (l <= r) {
        int mid = (l + r) / 2;
        if(check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    // if(ans == 6) ans += 3;
    cout << ans << endl;
    r0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 31836 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 165 ms 32004 KB Output is correct
4 Correct 156 ms 31832 KB Output is correct
5 Correct 173 ms 31992 KB Output is correct
6 Correct 155 ms 31836 KB Output is correct
7 Correct 164 ms 31996 KB Output is correct
8 Correct 161 ms 31836 KB Output is correct
9 Correct 165 ms 32000 KB Output is correct
10 Correct 168 ms 31992 KB Output is correct
11 Correct 156 ms 31832 KB Output is correct
12 Correct 164 ms 32000 KB Output is correct
13 Correct 161 ms 32000 KB Output is correct
14 Correct 166 ms 31992 KB Output is correct
15 Correct 185 ms 31996 KB Output is correct