oj.uz

Submission #377031

# Submission time Handle Problem Language Result Execution time Memory
377031 2021-03-12T19:40:25 Z SavicS Watching (JOI13_watching) C++14
100 / 100
 225 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){
				if(jp == 1){
					// ovde sve mogu sa jednom malom kamerom, tako da mi ni jedna velika kamera ne treba
					dp[i][j] = 0;		
					continue;
				}
				// 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 1 ms 364 KB Output is correct
7 Correct 67 ms 16236 KB Output is correct
8 Correct 68 ms 16108 KB Output is correct
9 Correct 71 ms 16108 KB Output is correct
10 Correct 69 ms 16108 KB Output is correct
11 Correct 67 ms 16108 KB Output is correct
12 Correct 67 ms 16108 KB Output is correct
13 Correct 68 ms 16108 KB Output is correct
14 Correct 68 ms 16108 KB Output is correct
15 Correct 66 ms 16236 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16164 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 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 75 ms 16108 KB Output is correct
8 Correct 86 ms 16108 KB Output is correct
9 Correct 135 ms 16236 KB Output is correct
10 Correct 225 ms 16164 KB Output is correct
11 Correct 80 ms 16108 KB Output is correct
12 Correct 154 ms 16236 KB Output is correct
13 Correct 75 ms 16108 KB Output is correct
14 Correct 73 ms 16116 KB Output is correct
15 Correct 72 ms 16164 KB Output is correct