Submission #298613

#	Time	Username	Problem	Language	Result	Execution time	Memory
298613		maximath_1	Watching (JOI13_watching)	C++17	100 / 100	196 ms	16252 KiB

watching

#include <iostream>
#include <array>
#include <vector>
#include <algorithm>
#include <string.h>
#include <set>
#include <math.h>
#include <numeric>
#include <assert.h>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <queue>
#include <random>
#include <chrono>
#include <deque>
#include <limits.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define endl "\n"
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST;
typedef tree<pair<int, int>, null_type, less_equal<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update> OST_multiset;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const ll inf = 1e9 + 69;
const ll infll = inf * 1ll * inf;
const ld pi = 3.14159265358979323L;
const ld eps = 1e-15;
 
void setIn(string s){freopen(s.c_str(), "r", stdin);}
void setOut(string s){freopen(s.c_str(), "w", stdout);}
void unsyncIO(){cin.tie(0) -> sync_with_stdio(0);}
int setIO_count = 0;
void setIO(string s = "", bool inx = 0, bool outx = 0){
	if(!setIO_count){
		unsyncIO();
		setIO_count = 1;
	}
	if(s.size()){ //output only
		if(inx) setIn(s + ".in");
		if(outx) setOut(s + ".out");
	}
}
 
#define gc getchar//_unlocked //can't for window server
#define pc putchar//_unlocked //can't for window server
ll inp(){
	char c = gc(); bool neg = false;
	for(; c < '0'||'9' < c; c = gc())
		if(c == '-') neg=true;
	ll rs = c - '0'; c = gc();
	for(; '0' <= c && c <= '9'; c = gc())
		rs = (rs << 1) + (rs << 3) + (c - '0');
	if(neg) rs = -rs;
	return rs;
}
void pri(ll _n){
	ll N = _n, rev, count = 0;
	bool neg = false;
	if(N < 0){
		N = -N; neg = true;
	}
	rev = N;
	if(N == 0) {pc('0'); return;}
	if(neg) pc('-');
	while(rev % 10 == 0) {count ++; rev /= 10;}
	rev = 0;
	while(N != 0) {rev = (rev << 3) + (rev << 1) + N % 10; N /= 10;}
	while(rev != 0) {pc(rev % 10 + '0'); rev /= 10;}
	while(count --) pc('0');
}
 
const ll mod = 998244353;
const int N = 2005;

int n, p, q, v[N], dp[N][N];

bool check(int wt){
	memset(dp, 0, sizeof(dp));

	for(int i = 1, j = 1, k = 1; i <= n; i ++){
		while(v[i] - v[j] >= wt) j ++;
		while(v[i] - v[k] >= wt * 2) k ++;

		dp[i][0] = dp[j - 1][0] + 1;
		for(int l = 1; l <= q; l ++)
			dp[i][l] = min(dp[j - 1][l] + 1, dp[k - 1][l - 1]);
	}

	for(int i = 0; i <= q; i ++)
		if(dp[n][i] <= p) return 1;
	return 0;
}

int main(){
	setIO();

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

	if(n <= p + q){
		cout << 1 << endl;
		return 0;
	}

	int lf = 1, rg = 1000000000, rs = rg;
	for(int md; lf <= rg;){
		md = (lf + rg) / 2;
		if(check(md)){
			rs = md; rg = md - 1;
		}else lf = md + 1;
	}

	cout << rs << endl;

	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'void setIn(std::string)':
watching.cpp:35:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   35 | void setIn(string s){freopen(s.c_str(), "r", stdin);}
      |                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
watching.cpp: In function 'void setOut(std::string)':
watching.cpp:36:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   36 | void setOut(string s){freopen(s.c_str(), "w", stdout);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 50 / 50