oj.uz

Submission #792932

# Submission time Handle Problem Language Result Execution time Memory
792932 2023-07-25T11:11:32 Z Cookie Watching (JOI13_watching) C++14
100 / 100
 734 ms 16052 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("FEEDING.INP");
ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const ld PI = 3.14159265359;
using u128 = __uint128_t;
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
const ll mod = 1e9 + 7, inf = 1e9;
const int mxn = 3e5 + 5;
int n, p, q;
int dp[2005][2005], a[2005];
bool ck(int mid){
    forr(i, 1, n + 2){
        forr(j, 0, p + 1){
            dp[i][j] = inf;
        }
    }
    dp[1][0] = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= p; j++){
            if(dp[i][j] == inf)continue;
            if(j != p){
                int idlw = upper_bound(a + 1, a + n + 1, a[i] + mid - 1) - a;
                dp[idlw][j + 1] = min(dp[idlw][j + 1], dp[i][j]);
            }
            int idhg = upper_bound(a + 1, a + n + 1, a[i] + 2 * mid - 1) - a;
            dp[idhg][j] = min(dp[idhg][j], dp[i][j] + 1);
            
        }
    }
    for(int i = 0; i <= p; i++){
        if(dp[n + 1][i] <= q)return(1);
    }
    return(0);
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> p >> q; p = min(p, n);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    
    
    int l = 0, r = 5e8, ans = -1;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(ck(mid)){
            ans = mid; r = mid - 1;
        }else{
            l = mid + 1;
        }
    }
    cout << ans;
    
    return(0);
}

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 3 ms 716 KB Output is correct
5 Correct 3 ms 716 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 1 ms 724 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 2 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 724 KB Output is correct
15 Correct 1 ms 724 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8284 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 627 ms 16048 KB Output is correct
4 Correct 690 ms 16048 KB Output is correct
5 Correct 81 ms 8916 KB Output is correct
6 Correct 715 ms 16044 KB Output is correct
7 Correct 6 ms 8404 KB Output is correct
8 Correct 75 ms 9352 KB Output is correct
9 Correct 281 ms 14264 KB Output is correct
10 Correct 734 ms 16052 KB Output is correct
11 Correct 86 ms 9064 KB Output is correct
12 Correct 581 ms 16040 KB Output is correct
13 Correct 6 ms 8404 KB Output is correct
14 Correct 9 ms 8408 KB Output is correct
15 Correct 7 ms 8404 KB Output is correct