oj.uz

Submission #522454

# Submission time Handle Problem Language Result Execution time Memory
522454 2022-02-05T04:16:19 Z hohohaha Watching (JOI13_watching) C++14
100 / 100
 167 ms 31784 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
#include "bits/stdc++.h"

using namespace std;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)
#define forIT(it, begin, end) for(__typeof(end) it = (begin) + ((begin) > (end)); it != (end) - ((begin) > (end)); it += 1 - 2 * ((begin) > (end)))
#define b_e(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
   fastio;
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;
const int maxn = 2005; 
int n, p, q; 
int arr[maxn]; 
int to[maxn]; 
int t2[maxn];
int dp[maxn][maxn]; 
bool ok(int w) { 
	int pt = n; 
	ford(i, n, 1) { 
		while(arr[pt] - arr[i] >= w) --pt; 
		to[i] = pt;
	}
	pt = n; 
	ford(i, n, 1) { 
		while(arr[pt] -  arr[i] >= 2 * w) --pt; 
		t2[i] = pt; 
	}
	fori(i, 0, n) fori(j, 0, n) dp[i][j] = 0; 
	fori(i, 0, p) fori(j, 0, q) { 
		int idx = dp[i][j]; 
		if(idx == n) return 1; 
		dp[i + 1][j] = max(dp[i + 1][j], to[dp[i][j] + 1]); 
		dp[i][j + 1] = max(dp[i][j + 1], t2[dp[i][j] + 1]); 
	}
	return 0; 
}
void solve() {
	cin >> n >> p >> q; p = min(p, n); q = min(q, n); 
	fori(i, 1, n) cin >> arr[i]; 
	sort(arr + 1, arr + n + 1); 
	int lo = 1, hi = 1e9; 
	while(lo < hi) { 
		int mi = lo + hi >> 1; 
		if(ok(mi)) hi = mi; 
		else lo = mi + 1; 
	}
	cout << lo; 
}

Compilation message

watching.cpp: In function 'void solve()':
watching.cpp:91:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   91 |   int mi = lo + hi >> 1;
      |            ~~~^~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 1 ms 832 KB Output is correct
7 Correct 1 ms 704 KB Output is correct
8 Correct 1 ms 816 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 704 KB Output is correct
12 Correct 2 ms 716 KB Output is correct
13 Correct 1 ms 716 KB Output is correct
14 Correct 1 ms 716 KB Output is correct
15 Correct 1 ms 716 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 31708 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 144 ms 31692 KB Output is correct
4 Correct 133 ms 31692 KB Output is correct
5 Correct 121 ms 31720 KB Output is correct
6 Correct 115 ms 31732 KB Output is correct
7 Correct 123 ms 31692 KB Output is correct
8 Correct 133 ms 31780 KB Output is correct
9 Correct 123 ms 31696 KB Output is correct
10 Correct 130 ms 31784 KB Output is correct
11 Correct 125 ms 31692 KB Output is correct
12 Correct 167 ms 31780 KB Output is correct
13 Correct 123 ms 31780 KB Output is correct
14 Correct 119 ms 31692 KB Output is correct
15 Correct 121 ms 31784 KB Output is correct