oj.uz

Submission #867425

# Submission time Handle Problem Language Result Execution time Memory
867425 2023-10-28T11:16:43 Z Cookie Watching (JOI13_watching) C++14
100 / 100
 402 ms 64228 KB 
#include<bits/stdc++.h>
#include<fstream>
using namespace std;
ifstream fin("nondec.in");
ofstream fout("nondec.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;
const int mxn = 2e5 + 5, mxq = 2e5 + 5, sq = 500, mxv = 1e7 + 5;
const ll inf = 1e9;
//const int base= (1 << 18);
int n, a, b;
ll x[mxn + 1];
pll dp[2005][2005];
void ckmin(pll &a, pll b){
    if(b.fi < a.fi)a = b;
    else if(a.fi == b.fi && b.se > a.se)a = b;
}
bool ck(ll mid){
    forr(i, 1, n + 1){
        forr(j, 0, a + 1){
            dp[i][j] = make_pair(inf, 0);
        }
    }
    dp[1][0] = make_pair(1, 2 * mid - 1);
    dp[1][1] = make_pair(0, mid - 1);
    for(int i = 1; i < n; i++){
        for(int j = 0; j <= a; j++){
            if(dp[i][j].first == inf)continue;
            if(dp[i][j].second >= x[i + 1] - x[i]){
                ckmin(dp[i + 1][j], make_pair(dp[i][j].first, dp[i][j].second - (x[i + 1] - x[i])));
            }if(j < a){
                ckmin(dp[i + 1][j + 1], make_pair(dp[i][j].first, mid - 1));
            }ckmin(dp[i + 1][j], make_pair(dp[i][j].first + 1, mid * 2 - 1));
        }
    }
    for(int i = 0; i <= a; i++){
        if(dp[n][i].first <= b)return(1);
    }
    return(0);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> a >> b;
  if(a + b >= n){
	cout << 1;
    return(0);
  }
    for(int i = 1; i <= n; i++)cin >> x[i];
    sort(x + 1, x + n + 1);
    ll l = 1, r = 1e9, ans;
    while(l <= r){
        ll 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 6492 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 2 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6488 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 64052 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 424 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 10 ms 64100 KB Output is correct
8 Correct 33 ms 64088 KB Output is correct
9 Correct 198 ms 64160 KB Output is correct
10 Correct 402 ms 64228 KB Output is correct
11 Correct 26 ms 64108 KB Output is correct
12 Correct 246 ms 64176 KB Output is correct
13 Correct 10 ms 64092 KB Output is correct
14 Correct 12 ms 64092 KB Output is correct
15 Correct 11 ms 64092 KB Output is correct