Submission #261092

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
261092	2020-08-11T11:29:39 Z	srj	Watching (JOI13_watching)	C++14	100 / 100	715 ms	31992 KB

watching

#include<bits/stdc++.h>
// #include<gondola.h>
#define pb push_back
#define mp make_pair
#define forn(i,a,b) for(int i =a;i<b;i++)
#define fi first
#define se second
#define fast ios_base::sync_with_stdio(false);
using namespace std;

//for debugging 
/*
g++ -D_GLIBCXX_ASSERTIONS -DDEBUG -ggdb3 -std=c++14 
*/
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os,  const Cont& v){
	os<<"[";
	for(auto& x:v){os<<x<<", ";}
	return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os,  const pair<Ts...>& p){
	return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// debugging ends here

typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int INF = 1e8;
const int mxn = 2005;
const int mxp  = 1e5+1;
ll cache[mxn][mxn];

ll p,q;
ll a[mxn];
ll n;

ll dp(ll i, ll pres, ll w) {
	//cerr << "i=" << i << "; pres=" << pres << endl;
	// caso base
	if (i >= n) return 0LL;
	
	// caso dp
	if (cache[i][pres]!=-1) return cache[i][pres];
	// caso recursivo
	else {
		ll res1 = INF, res2 = INF;
		
		// tomo un p
		ll j=i;
		while (j+1<n && a[j+1]-a[i]+1<=w) j++;
		if (pres) res1 = dp(j+1, pres-1, w);
		
		while (j+1<n && a[j+1]-a[i]+1<=2*w) j++;
		res2 = dp(j+1, pres, w) + 1LL;
		
		return cache[i][pres] = min(res1, res2);
	}
}

int main(){
	// #ifndef ONLINE_JUDGE
	// freopen("bbreeds.in","r",stdin);
	// freopen("bbreeds.out","w",stdout);
	// #endif
	// ll n;
	cin >> n >> p >> q;
	// ll a[n];
	// dbg(n);
	for(ll i =0;i<n;i++)
		cin >> a[i];
	sort(a,a+n);

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

	ll lo = 1,hi = 1e9;
	while(lo<=hi){
		ll mid  = lo + (hi-lo)/2;
		// cout << mid << endl; 
		memset(cache,-1,sizeof(cache));
		ll check = dp(0,p,mid);
		// cout << lo << endl;
		// cout << mid << " " << cache[n-1][p] << endl;
		if(check<=q)
			hi = mid-1;
		else lo = mid+1;
	}
	cout << lo << endl;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	135 ms	31744 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	139 ms	31864 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	139 ms	31832 KB	Output is correct
8	Correct	140 ms	31744 KB	Output is correct
9	Correct	148 ms	31744 KB	Output is correct
10	Correct	135 ms	31840 KB	Output is correct
11	Correct	143 ms	31744 KB	Output is correct
12	Correct	140 ms	31864 KB	Output is correct
13	Correct	137 ms	31744 KB	Output is correct
14	Correct	136 ms	31836 KB	Output is correct
15	Correct	134 ms	31744 KB	Output is correct

Subtask #2

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	31864 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	2 ms	384 KB	Output is correct
7	Correct	143 ms	31864 KB	Output is correct
8	Correct	205 ms	31864 KB	Output is correct
9	Correct	359 ms	31992 KB	Output is correct
10	Correct	715 ms	31864 KB	Output is correct
11	Correct	222 ms	31992 KB	Output is correct
12	Correct	653 ms	31992 KB	Output is correct
13	Correct	143 ms	31864 KB	Output is correct
14	Correct	137 ms	31776 KB	Output is correct
15	Correct	139 ms	31864 KB	Output is correct