oj.uz

Submission #987325

# Submission time Handle Problem Language Result Execution time Memory
987325 2024-05-22T14:55:09 Z nikaa123 Watching (JOI13_watching) C++14
50 / 100
 84 ms 26972 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 = 0; 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 2 ms 2396 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 1 ms 2396 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 1 ms 860 KB Output is correct
13 Correct 1 ms 860 KB Output is correct
14 Correct 1 ms 856 KB Output is correct
15 Correct 2 ms 860 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8536 KB Output is correct
2 Correct 1 ms 344 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 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 10 ms 23900 KB Output is correct
8 Correct 84 ms 26972 KB Output is correct
9 Correct 16 ms 24504 KB Output is correct
10 Incorrect 14 ms 24156 KB Output isn't correct
11 Halted 0 ms 0 KB -