oj.uz

Submission #419607

# Submission time Handle Problem Language Result Execution time Memory
419607 2021-06-07T10:10:51 Z amunduzbaev Watching (JOI13_watching) C++14
100 / 100
 558 ms 32008 KB 
/* made by amunduzbaev */
 
//~ #include <ext/pb_ds/assoc_container.hpp>
//~ #include <ext/pb_ds/tree_policy.hpp>
#include "bits/stdc++.h"
 
using namespace std;
//~ using namespace __gnu_pbds;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define NeedForSpeed ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vv vector
#define mem(arr, v) memset(arr, v, sizeof arr)
#define int long long
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii; 
typedef vector<int> vii;
typedef vector<pii> vpii;
template<class T> bool umin(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T> bool umax(T& a, const T& b) { return a < b ? a = b, true : false; }
template<int sz> using tut = array<int, sz>;
void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);  
	freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
//~ template<class T> using oset = tree<T, 
//~ null_type, less_equal<T>, rb_tree_tag, 
//~ tree_order_statistics_node_update>;
 
const int N = 2e3+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
 
#define MULTI 0
int n, m, k, s, t, q, ans, res, a[N];
int W[N], dw[N], dp[N][N];;

int rec(int i, int j){
	int& res = dp[i][j];
	if(~res) return res;
	if(i > n) return res = 0;
	res = rec(dw[i], j) + 1;
	if(j) umin(res, rec(W[i], j - 1));
	return res;
}

bool check(int w){ mem(dp, -1);
	int l = 1, r = 1;
	for(;r<=n;r++){
		while(a[r] - a[l] + 1 > w) W[l] = r, l++;
	} while(l <= n) W[l] = r, l++;
	l = 1, r = 1;
	for(;r<=n;r++){
		while(a[r] - a[l] + 1 > 2 * w) dw[l] = r, l++;
	} while(l <= n) dw[l] = r, l++;
	return (rec(1, m) <= q);
}

void solve(int t_case){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(m + q > n) { cout<<1<<"\n"; return; }
	sort(a+1, a+n+1);
	a[0] = a[1];
	
	int l = 1, r = mod;
	while(l + 1 < r){
		int m = (l + r)>>1;
		if(check(m)) r = m;
		else l = m;
	} if(!check(l)) l = r;
	cout<<l<<"\n";
}

signed main(){
	NeedForSpeed
	if(MULTI){
		int t; cin>>t;
		for(int t_case = 1; t_case <= t; t_case++) solve(t_case);
	} else solve(1);
	return 0;
}

Compilation message

watching.cpp: In function 'void usaco(std::string)':
watching.cpp:32:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 | void usaco(string s) { freopen((s+".in").c_str(),"r",stdin);
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:33:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen((s+".out").c_str(),"w",stdout); NeedForSpeed }
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 31692 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 131 ms 31768 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 292 KB Output is correct
7 Correct 130 ms 31780 KB Output is correct
8 Correct 129 ms 31680 KB Output is correct
9 Correct 131 ms 31800 KB Output is correct
10 Correct 146 ms 31788 KB Output is correct
11 Correct 140 ms 31784 KB Output is correct
12 Correct 131 ms 31700 KB Output is correct
13 Correct 131 ms 31780 KB Output is correct
14 Correct 131 ms 31692 KB Output is correct
15 Correct 132 ms 31800 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 31820 KB Output is correct
2 Correct 127 ms 31780 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 356 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 133 ms 31828 KB Output is correct
8 Correct 163 ms 31804 KB Output is correct
9 Correct 272 ms 31864 KB Output is correct
10 Correct 558 ms 31920 KB Output is correct
11 Correct 177 ms 32008 KB Output is correct
12 Correct 434 ms 31904 KB Output is correct
13 Correct 138 ms 31832 KB Output is correct
14 Correct 137 ms 31832 KB Output is correct
15 Correct 152 ms 31836 KB Output is correct