oj.uz

Submission #261086

# Submission time Handle Problem Language Result Execution time Memory
261086 2020-08-11T11:24:12 Z srj Watching (JOI13_watching) C++14
50 / 100
 527 ms 32380 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][pres]!=-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);
		
		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
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 16000 KB Output is correct
2 Correct 66 ms 16000 KB Output is correct
3 Correct 69 ms 16000 KB Output is correct
4 Correct 69 ms 16128 KB Output is correct
5 Correct 72 ms 16000 KB Output is correct
6 Correct 69 ms 16000 KB Output is correct
7 Correct 76 ms 16000 KB Output is correct
8 Correct 67 ms 16000 KB Output is correct
9 Correct 67 ms 16000 KB Output is correct
10 Correct 65 ms 16000 KB Output is correct
11 Correct 68 ms 16000 KB Output is correct
12 Correct 67 ms 16000 KB Output is correct
13 Correct 66 ms 16000 KB Output is correct
14 Correct 66 ms 16000 KB Output is correct
15 Correct 62 ms 16000 KB Output is correct

Subtask #2
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16128 KB Output is correct
2 Correct 67 ms 16000 KB Output is correct
3 Correct 527 ms 16248 KB Output is correct
4 Runtime error 38 ms 32380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -