oj.uz

Submission #377032

# Submission time Handle Problem Language Result Execution time Memory
377032 2021-03-12T19:41:37 Z SavicS Watching (JOI13_watching) C++14
100 / 100
 202 ms 16236 KB 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define fb(i,b,a) for(int i=b;i>=a;i--)

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2005;
const int inf = 1e9 + 5;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

// os.order_of_key(k) the number of elements in the os less than k
// *os.find_by_order(k)  print the k-th smallest number in os(0-based)

int n, p, q;
ll niz[maxn];

// p, q <= 1e5 i n <= 2000
// naive: n^2 * p * q
 
// za a malih kamera, koliko mi treba velikih da slikam prvih i proslova - dp[a][i]
// dp[a][i] <= q return 1, else return 0

int dp[maxn][maxn];
bool check(ll x){
	int jp = 1;
	int jq = 1;
	memset(dp, 0, sizeof(dp));
	ff(i,1,n){

		while(niz[i] - niz[jp] >= x)jp += 1;
		while(niz[i] - niz[jq] >= 2 * x)jq += 1;
		
		ff(j,0,p){
			if(j != 0){
				// ili uradim sa malom kamerom [jp, i]
				// ili uradim sa velikom kamerom [jq, i], ali dodam jedan
				dp[i][j] = min(dp[jp - 1][j - 1], dp[jq - 1][j] + 1);
			}
			else dp[i][j] = dp[jq - 1][j] + 1;
		}
	}	
	int mn = inf;
	ff(j,0,p)mn = min(mn, dp[n][j]);
	return mn <= q;
}

int main()
{
   	ios::sync_with_stdio(false);
   	cout.tie(nullptr);
  	cin.tie(nullptr);
	cin >> n >> p >> q;
	ff(i,1,n)cin >> niz[i];
	
	if(p + q >= n)return cout << 1, 0;
	
	sort(niz + 1, niz + n + 1);
	
	int l = 1, r = inf, ans = inf;
	while(l <= r){
		int mid = (l + r) / 2;
		if(check(mid)){
			ans = mid;
			r = mid - 1;
		}
		else l = mid + 1;
	}
	cout << ans << endl;
   	return 0;
}
/**

3 1 1
2
11
17


// probati bojenje sahovski ili slicno

**/

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 16108 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 69 ms 16108 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 0 ms 364 KB Output is correct
7 Correct 67 ms 16108 KB Output is correct
8 Correct 64 ms 16108 KB Output is correct
9 Correct 66 ms 16108 KB Output is correct
10 Correct 68 ms 16108 KB Output is correct
11 Correct 72 ms 16108 KB Output is correct
12 Correct 66 ms 16108 KB Output is correct
13 Correct 67 ms 16108 KB Output is correct
14 Correct 64 ms 16236 KB Output is correct
15 Correct 64 ms 16108 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 16108 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 70 ms 16108 KB Output is correct
8 Correct 81 ms 16108 KB Output is correct
9 Correct 125 ms 16236 KB Output is correct
10 Correct 202 ms 16108 KB Output is correct
11 Correct 77 ms 16108 KB Output is correct
12 Correct 139 ms 16108 KB Output is correct
13 Correct 67 ms 16108 KB Output is correct
14 Correct 68 ms 16236 KB Output is correct
15 Correct 69 ms 16108 KB Output is correct