oj.uz

Submission #312907

# Submission time Handle Problem Language Result Execution time Memory
312907 2020-10-14T15:35:37 Z limabeans Watching (JOI13_watching) C++17
100 / 100
 217 ms 16076 KB 
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const int inf = 1e9;
const int maxn = 1e5 + 5;


int n,p,q;
int a[maxn];


int dp[2001][2001]; //dp[i][j]: min big cameras for first i events, given we use j small cameras

bool test(int len) {
    int l=1;
    int r=1;
    for (int i=1; i<=n; i++) {
	while (a[l] < a[i]-len+1) l++;
	while (a[r] < a[i]-2*len+1) r++;
	
	for (int j=0; j<=p; j++) {
	    dp[i][j] = inf;
	    if (j>0) {
		dp[i][j] = min(dp[i][j], dp[l-1][j-1]);
	    }
	    dp[i][j] = min(dp[i][j], dp[r-1][j] + 1);
	}
    }

    return dp[n][p] <= q;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);

    cin>>n>>p>>q;
    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    sort(a+1,a+1+n);

    if (p+q>=n) out(1);

    int lo=0;
    int hi=1e9;

    while (hi-lo>1) {
	int mid=(lo+hi)/2;
	if (test(mid)) {
	    hi=mid;
	} else {
	    lo=mid;
	}
    }

    cout<<hi<<endl;
    
    
    return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 416 KB Output is correct
4 Correct 1 ms 416 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 768 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 1 ms 768 KB Output is correct
11 Correct 1 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 1 ms 768 KB Output is correct
14 Correct 1 ms 768 KB Output is correct
15 Correct 1 ms 768 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8320 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 7 ms 8448 KB Output is correct
8 Correct 21 ms 9344 KB Output is correct
9 Correct 98 ms 14336 KB Output is correct
10 Correct 217 ms 16076 KB Output is correct
11 Correct 16 ms 9088 KB Output is correct
12 Correct 123 ms 16000 KB Output is correct
13 Correct 7 ms 8448 KB Output is correct
14 Correct 8 ms 8576 KB Output is correct
15 Correct 8 ms 8576 KB Output is correct