oj.uz

Submission #261082

# Submission time Handle Problem Language Result Execution time Memory
261082 2020-08-11T11:20:27 Z srj Watching (JOI13_watching) C++14
0 / 100
 1000 ms 16128 KB 
#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 = 1e9;
const int mxn = 2005;
int cache[mxn+1][mxn];

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

ll dp(int i, ll pres, ll w) {
	//cerr << "i=" << i << "; pres=" << pres << endl;
	// caso base
	if (i >= n) return 0LL;
	
	// caso dp
	if (cache[i][p]!=-1) return cache[i][pres];
	// caso recursivo
	else {
		ll res1 = INF, res2 = INF;
		
		// tomo un p
		int j=i;
		while (j+1<n && a[j+1]-a[i]+1<=w) j++;
		if (pres) res1 = dp(j+1, pres-1, w);
		
		// tomo un q
		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
	// int n;
	cin >> n >> p >> q;
	// int a[n];
	// dbg(n);
	for(int i =0;i<n;i++)
		cin >> a[i];
	sort(a,a+n);
	int lo = 1,hi = 1e9;
	while(lo<=hi){
		int mid  = lo + (hi-lo)/2;
		// cout << mid << endl; 
		memset(cache,-1,sizeof(cache));
		int 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
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 16000 KB Output is correct
2 Correct 82 ms 16000 KB Output is correct
3 Correct 86 ms 16000 KB Output is correct
4 Execution timed out 1062 ms 16000 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 16128 KB Output is correct
2 Correct 83 ms 16108 KB Output is correct
3 Execution timed out 1089 ms 16128 KB Time limit exceeded
4 Halted 0 ms 0 KB -