oj.uz

Submission #987330

# Submission time Handle Problem Language Result Execution time Memory
987330 2024-05-22T14:59:16 Z nikaa123 Watching (JOI13_watching) C++14
100 / 100
 175 ms 31836 KB 
// #pragma GCC diagnostic warnign "-std=c++11"
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pp pop_back
#define endl '\n'
#define ff first
#define ss second
#define stop exit(0)
#define sz(x) (int)x.size()
#define pause system("pause")
#define all(x) (x).begin(),(x).end()
#define deb(x) cout << #x << "-" << x  << endl
 
typedef char chr;
typedef string str;
typedef long long ll;
typedef vector <int> vii;
typedef pair <int,int> pii;
 
const long long INF = LLONG_MAX;
const int inf = INT_MAX;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
const double PI = 2 * acos(0.0);

const int N = 2e3 + 5;

int n,p,q,arr[N],ans;
int dp[N][N];

bool check(int w) {
    vector <int> s;
    s.push_back(-INF);
    for (int i = 1; i <= n; i++) {
        s.pb(arr[i]);
        int l1 = (lower_bound(all(s),arr[i]-w+1))-s.begin();
        int l2 = (lower_bound(all(s),arr[i]-2*w+1)-s.begin());
        for (int j = 0; j <= q; j++) {
            
            
            dp[i][j] = dp[l1-1][j]+1;
            
            
            if (j) dp[i][j] = min(dp[i][j],dp[l2-1][j-1]);
        }
    }
    for (int i = 0; i <= q; i++) {
        if (dp[n][i] <= p) return true;
    }
    return false;
}

inline void test_case () {     

    cin >> n >> p >> q;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    sort(arr+1,arr+1+n);
    if (p+q >= n) {
        cout << 1 << endl;
        return;
    }
    int l = 1; int r = 2*1e9;
    while (l <= r) {
        int mid = (l+r)/2;
        dp[0][0] = 0;
        if (check(mid)) {
            ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    cout << ans << endl;

}
 
signed main () {
 
    ios_base :: sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int T = 1;
    // cin >> T;
    while(T--) {
        test_case();
    }
    
    return 0;
 
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 2 ms 2396 KB Output is correct
11 Correct 1 ms 2564 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 1 ms 2392 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 10 ms 26688 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 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 11 ms 28252 KB Output is correct
8 Correct 71 ms 29392 KB Output is correct
9 Correct 19 ms 27228 KB Output is correct
10 Correct 15 ms 28508 KB Output is correct
11 Correct 175 ms 31836 KB Output is correct
12 Correct 96 ms 30556 KB Output is correct
13 Correct 9 ms 28248 KB Output is correct
14 Correct 7 ms 25176 KB Output is correct
15 Correct 8 ms 22364 KB Output is correct