oj.uz

Submission #839291

# Submission time Handle Problem Language Result Execution time Memory
839291 2023-08-29T15:24:55 Z hafo Watching (JOI13_watching) C++14
100 / 100
 159 ms 16068 KB 
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define Size(x) (int) x.size()
#define all(x) x.begin(), x.end()
using namespace std;

template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}

const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 2e3 + 7;
const ll oo = 1e9 + 69;

int n, p, q, a[maxn], dp[maxn][maxn];

bool check(int w) {
    for(int i = 1; i <= n; i++) {
        int l1 = lower_bound(a + 1, a + 1 + n, a[i] - w + 1) - a;
        int l2 = lower_bound(a + 1, a + 1 + n, a[i] - 2 * w + 1) - a;
        for(int j = 0; j <= p; j++) {
            dp[i][j] = oo;
            if(j > 0) mini(dp[i][j], dp[l1 - 1][j - 1]);
            mini(dp[i][j], dp[l2 - 1][j] + 1);
            if(i == n && dp[i][j] <= q) return 1;
        }
    }
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);

    cin>>n>>p>>q;
    mini(p, n);
    mini(q, n);
    for(int i = 1; i <= n; i++) cin>>a[i];
    sort(a + 1, a + 1 + n);
    
    int l = 1, r = 1e9, mid, res;
    while(l <= r) {
        mid = l + r >> 1;
        if(check(mid)) {
            res = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout<<res;
    return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |         mid = l + r >> 1;
      |               ~~^~~
watching.cpp:59:11: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   59 |     cout<<res;
      |           ^~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 716 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 712 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 848 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8276 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 126 ms 16068 KB Output is correct
4 Correct 159 ms 16036 KB Output is correct
5 Correct 13 ms 8916 KB Output is correct
6 Correct 155 ms 16036 KB Output is correct
7 Correct 7 ms 8404 KB Output is correct
8 Correct 17 ms 9424 KB Output is correct
9 Correct 65 ms 14164 KB Output is correct
10 Correct 153 ms 16040 KB Output is correct
11 Correct 14 ms 9112 KB Output is correct
12 Correct 92 ms 16032 KB Output is correct
13 Correct 10 ms 8404 KB Output is correct
14 Correct 9 ms 8404 KB Output is correct
15 Correct 9 ms 8404 KB Output is correct