oj.uz

Submission #261088

# Submission time Handle Problem Language Result Execution time Memory
261088 2020-08-11T11:26:26 Z srj Watching (JOI13_watching) C++14
50 / 100
 860 ms 64248 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 = 1e8;
const int mxn = 2005;
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);
	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 137 ms 31864 KB Output is correct
2 Correct 129 ms 31744 KB Output is correct
3 Correct 133 ms 31744 KB Output is correct
4 Correct 131 ms 31736 KB Output is correct
5 Correct 131 ms 31744 KB Output is correct
6 Correct 132 ms 31832 KB Output is correct
7 Correct 134 ms 31804 KB Output is correct
8 Correct 131 ms 31744 KB Output is correct
9 Correct 135 ms 31744 KB Output is correct
10 Correct 130 ms 31744 KB Output is correct
11 Correct 142 ms 31744 KB Output is correct
12 Correct 137 ms 31848 KB Output is correct
13 Correct 136 ms 31744 KB Output is correct
14 Correct 129 ms 31896 KB Output is correct
15 Correct 130 ms 31736 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 31844 KB Output is correct
2 Correct 132 ms 31864 KB Output is correct
3 Correct 860 ms 31992 KB Output is correct
4 Runtime error 73 ms 64248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -