Submission #187523

#	Time	Username	Problem	Language	Result	Execution time	Memory
187523		dndhk	Watching (JOI13_watching)	C++14	50 / 100	1061 ms	95500 KiB

watching

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX_N = 2000;
const ll INFLL = 10000;
int N, P, Q;
vector<ll> v;

ll dp[MAX_N+1][MAX_N+1];
priority_queue<pll, vector<pll>, greater<pll> > pq[MAX_N+1];

int lb(ll x){
	//cout<<"?"<<x<<" ";
	int s = 1, e = v.size()-1, m;
	while(s<e){
		m = (s+e)/2+1;
		//cout<<m<<" "<<v[m]<<endl;

		if(v[m]<=x)	s = m;
		else	e = m-1;
	}
	//cout<<s<<endl;
	return s;
}

bool chk(ll x){
	for(int i=0; i<=N; i++){
		for(int j=0; j<=N; j++)	dp[i][j] = INFLL;
		while(!pq[i].empty())	pq[i].pop();
	}
	dp[0][0] = 0LL;
	//cout<<x<<endl;
	for(int i=0; i<=N; i++){
		for(int j=N; j>=0; j--){
			if(!pq[j].empty()){
				while(!pq[j].empty() && pq[j].top().second<i)	pq[j].pop();
				if(!pq[j].empty()){
					dp[i][j] = pq[j].top().first;
				}	
			}
			//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
			if(dp[i][j]==INFLL || i==N)	continue;
			ll k = dp[i][j];
			ll l = v[i+1], r1 = lb(l+x-1LL), r2 = lb(l+2LL*x-1LL);
			//cout<<"*"<<l<<" "<<r1<<" "<<r2<<endl;
			pq[j+1].push({k, r1});
			pq[j].push({k+1, r2});
		}
	}
	for(int i=0; i<=P; i++){
		if(dp[N][i]<=Q)	return true;
	}
	return false;
}

int main(){
	scanf("%d%d%d", &N, &P, &Q);	
	v.pb(0);
	for(int i=1; i<=N; i++){
		ll x; scanf("%lld", &x);
		v.pb(x);
	}
	sort(v.begin(), v.end());
	v.erase(unique(v.begin(), v.end()), v.end());
	N = v.size()-1;
	ll s = 1LL, e = 1000000000LL, m;
	while(s<e){
		m = (s+e)/2LL;
		if(chk(m)){
			e = m;
		}else{
			s = m+1;
		}
	}
	printf("%lld", s);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &P, &Q); 
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x);
         ~~~~~^~~~~~~~~~~~

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50