Submission #888967

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
888967	2023-12-18T13:29:04 Z	dwuy	Watching (JOI13_watching)	C++14	100 / 100	211 ms	32084 KB

watching

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""
#define int long long

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 2005;

int n, p, q;
int a[MX];
int dp[MX][MX];
/// dp[i][j] : least large camera to check a[1, i], used j small camera;

void nhap(){
    cin >> n >> p >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    if(p+q>=n){
        cout << 1;
        exit(0);
    }
    sort(a+1, a+1+n);
}

bool ok(int mid){
    memset(dp, 0x3f, sizeof dp);
    memset(dp[0], 0, sizeof dp[0]);
    for(int i=1, sm=1, bg=1; i<=n; i++){
        while(a[i] - a[sm] + 1 > mid) sm++;
        while(a[i] - a[bg] + 1 > mid+mid) bg++;
        for(int j=0; j<=p; j++){
            dp[i][j] = min({dp[i][j], (j? dp[sm-1][j-1] : INF), dp[bg-1][j] + 1});
        }
    }
    return dp[n][p] <= q;
}

void solve(){
    int res = 0;
    for(int lo=1, hi=1000000000; lo<=hi;){
        int mid = (lo+hi)>>1;
        if(ok(mid)) res = mid, hi = mid - 1;
        else lo = mid + 1;
    }
    cout << res;
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	31836 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	65 ms	31912 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	66 ms	31832 KB	Output is correct
8	Correct	63 ms	31912 KB	Output is correct
9	Correct	66 ms	31836 KB	Output is correct
10	Correct	63 ms	31836 KB	Output is correct
11	Correct	66 ms	31836 KB	Output is correct
12	Correct	67 ms	31836 KB	Output is correct
13	Correct	67 ms	31832 KB	Output is correct
14	Correct	63 ms	31916 KB	Output is correct
15	Correct	64 ms	31916 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	68 ms	31920 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	70 ms	31836 KB	Output is correct
8	Correct	80 ms	31936 KB	Output is correct
9	Correct	132 ms	32084 KB	Output is correct
10	Correct	211 ms	31936 KB	Output is correct
11	Correct	75 ms	31832 KB	Output is correct
12	Correct	149 ms	31836 KB	Output is correct
13	Correct	67 ms	31936 KB	Output is correct
14	Correct	73 ms	31940 KB	Output is correct
15	Correct	70 ms	31944 KB	Output is correct