oj.uz

Submission #535938

# Submission time Handle Problem Language Result Execution time Memory
535938 2022-03-11T22:37:08 Z michao Watching (JOI13_watching) C++14
100 / 100
 314 ms 31796 KB 
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=2005;
const int inf=(int)1e9+9;
int a[MAX];
int dp[MAX][MAX];
int r1[MAX];
int r2[MAX];
int n,p,q;
bool check(int mid){
	for (int i=0;i<=n;i++)for (int j=0;j<=n;j++)dp[i][j]=0;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++){
			if (a[j]-a[i]+1<=mid)r1[i]=j;
			if (a[j]-a[i]+1<=mid*2)r2[i]=j;
		}
	}
	for (int i=0;i<=p;i++){
		for (int j=0;j<=q;j++){
			if (dp[i][j]==n)return true;
			int l=dp[i][j]+1;
			if (i!=p)
			dp[i+1][j]=max(dp[i+1][j],r1[l]);
			if (j!=q)
			dp[i][j+1]=max(dp[i][j+1],r2[l]);
		}
	}
	return false;
}
int32_t main(){
  BOOST;
  cin>>n>>p>>q;
  p=min(p,n);
  q=min(q,n);
  for (int i=1;i<=n;i++)cin>>a[i];
  sort(a+1,a+n+1);
  int ip=0,ik=inf;
  while (ip+1<ik){
		int mid=(ip+ik)>>1;
		if (check(mid))ik=mid;
		else ip=mid;
  }
  cout<<ik;
  return 0; 
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 716 KB Output is correct
7 Correct 1 ms 716 KB Output is correct
8 Correct 1 ms 724 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 716 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct
14 Correct 2 ms 716 KB Output is correct
15 Correct 2 ms 720 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 31752 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 282 ms 31784 KB Output is correct
4 Correct 266 ms 31784 KB Output is correct
5 Correct 243 ms 31784 KB Output is correct
6 Correct 253 ms 31784 KB Output is correct
7 Correct 246 ms 31784 KB Output is correct
8 Correct 255 ms 31796 KB Output is correct
9 Correct 271 ms 31788 KB Output is correct
10 Correct 282 ms 31788 KB Output is correct
11 Correct 287 ms 31780 KB Output is correct
12 Correct 314 ms 31788 KB Output is correct
13 Correct 245 ms 31784 KB Output is correct
14 Correct 245 ms 31792 KB Output is correct
15 Correct 247 ms 31784 KB Output is correct