oj.uz

Submission #704913

# Submission time Handle Problem Language Result Execution time Memory
704913 2023-03-03T06:43:13 Z RandomLB Watching (JOI13_watching) C++17
100 / 100
 164 ms 16084 KB 
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
#define siz(x) (int)x.size()
#define ms(x, a) memset(x, a, sizeof(x))
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values){
    cout << vars << " = ";
    string delim = "";
    (...,(cout << delim << values, delim = ", "));
    cout << endl;
}
const int INF = 0x3f3f3f3f;
//==================================
const int MAX = 2005;
int arr[MAX], dp[MAX][MAX], n, p, q;

inline int bs(int i, int x){
    int l = 0, r = i;
    while (l+1 < r){
        int m = l+(r-l)/2;
        if (arr[i]-arr[m]+1 <= x) r = m; else l = m;
    }
    return r;
}

bool good(int w){
    ms(dp, 0);
    for (int i = 1; i <= n; i++){
        int x = bs(i, w)-1, y = bs(i, 2*w)-1;
        for (int j = 0; j <= p; j++){
            dp[i][j] = min((j? dp[x][j-1] : INF), dp[y][j]+1);
        }
    }
    return dp[n][p] <= q;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> p >> q;
    if (p+q >= n){ cout << 1 << "\n"; return 0; }
    for (int i = 1; i <= n; i++) cin >> arr[i];
    sort(arr+1, arr+n+1);
    int l = 1, r = INF;
    while (l+1 < r){
        int m = l+(r-l)/2;
        (good(m)? r : l) = m;
    }
    cout << r << "\n";
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 16032 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 52 ms 15956 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 54 ms 16040 KB Output is correct
8 Correct 55 ms 16048 KB Output is correct
9 Correct 52 ms 15980 KB Output is correct
10 Correct 52 ms 16064 KB Output is correct
11 Correct 58 ms 15956 KB Output is correct
12 Correct 58 ms 15956 KB Output is correct
13 Correct 55 ms 16036 KB Output is correct
14 Correct 52 ms 15956 KB Output is correct
15 Correct 52 ms 16040 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 16056 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 60 ms 16068 KB Output is correct
8 Correct 66 ms 16060 KB Output is correct
9 Correct 106 ms 15956 KB Output is correct
10 Correct 164 ms 16064 KB Output is correct
11 Correct 68 ms 16064 KB Output is correct
12 Correct 124 ms 15964 KB Output is correct
13 Correct 58 ms 16084 KB Output is correct
14 Correct 60 ms 16068 KB Output is correct
15 Correct 61 ms 16060 KB Output is correct