Submission #208134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208134	2020-03-10T04:58:48 Z	YJU	Watching (JOI13_watching)	C++17	50 / 100	1000 ms	32052 KB

watching

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll MOD=1e9+7;
const ll N=2e3+5;
const ld pi=3.14159265359;
const ll INF=(1LL<<62);
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define setp setprecision
#define lwb lower_bound
#define SZ(a) (ll)a.size()

ll n,P,Q,x,DP[N][N];
vector<ll> v;

bool b(ll k){
	memset(DP,0,sizeof(DP));
	DP[0][0]=0;
	REP(i,P+1)REP(j,Q+1){
		DP[i][j+1]=max(DP[i][j+1],(ll)(lwb(v.begin(),v.end(),v[DP[i][j]]+2*k)-v.begin()));
		DP[i+1][j]=max(DP[i+1][j],(ll)(lwb(v.begin(),v.end(),v[DP[i][j]]+1*k)-v.begin()));
		if(DP[i][j]==n)return 1;
	}
	return 0;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>P>>Q;
	P=min(P,n);Q=min(Q,n);
	REP(i,n)cin>>x,v.pb(x);
	sort(v.begin(),v.end());
	ll l=-1,r=MOD;
	while(r-l>1){
		(b((r+l)/2)?r=(r+l)/2:l=(r+l)/2);
	}
	cout<<r<<"\n";
	return 0;
}

Subtask #1

50.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	133 ms	31736 KB	Output is correct
2	Correct	134 ms	31736 KB	Output is correct
3	Correct	134 ms	31736 KB	Output is correct
4	Correct	136 ms	31736 KB	Output is correct
5	Correct	134 ms	31864 KB	Output is correct
6	Correct	136 ms	31736 KB	Output is correct
7	Correct	138 ms	32052 KB	Output is correct
8	Correct	135 ms	31736 KB	Output is correct
9	Correct	136 ms	31736 KB	Output is correct
10	Correct	137 ms	31736 KB	Output is correct
11	Correct	132 ms	31864 KB	Output is correct
12	Correct	136 ms	31740 KB	Output is correct
13	Correct	133 ms	31856 KB	Output is correct
14	Correct	137 ms	31736 KB	Output is correct
15	Correct	136 ms	31736 KB	Output is correct

Subtask #2

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	138 ms	31864 KB	Output is correct
2	Correct	141 ms	31992 KB	Output is correct
3	Correct	615 ms	31864 KB	Output is correct
4	Correct	267 ms	31864 KB	Output is correct
5	Correct	143 ms	31864 KB	Output is correct
6	Correct	203 ms	31864 KB	Output is correct
7	Correct	137 ms	31992 KB	Output is correct
8	Correct	261 ms	31864 KB	Output is correct
9	Correct	243 ms	31864 KB	Output is correct
10	Correct	276 ms	31992 KB	Output is correct
11	Correct	230 ms	31864 KB	Output is correct
12	Execution timed out	1066 ms	31992 KB	Time limit exceeded
13	Halted	0 ms	0 KB	-