oj.uz

Submission #443973

# Submission time Handle Problem Language Result Execution time Memory
443973 2021-07-12T17:09:27 Z Khizri Watching (JOI13_watching) C++17
100 / 100
 817 ms 31788 KB 
#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll long long
#define pb push_back		 
#define F first																 
#define S second 															 
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
	if(a>b) swap(a,b);
	if(a==0) return a+b;
	return gcd(b%a,a);
}
ll lcm(ll a,ll b){
	return a/gcd(a,b)*b;
}
bool is_prime(ll n){
	ll k=sqrt(n);
	if(n==2) return true;
	if(n<2||n%2==0||k*k==n) return false;
	for(int i=3;i<=k;i+=2){
		if(n%i==0){
			return false;
		}
	}
	return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=2000+5;
ll t=1,n,arr[mxn],a,b,color[mxn],dp[mxn][mxn];
vector<ll>vt;
ll cal(int ind,ll dis){
	ll k=vt[min(ind,(int)vt.size()-1)]+dis-1;
	ll ans=ind;
	for(int i=ind;i<vt.size();i++){
		if(vt[i]<=k){
			ans++;
		}
		else{
			break;
		}
	}
	return ans;
}
int check(int x,int y,ll dis){
	x=min(n,x*1ll);
	y=min(n,y*1ll);
	dp[0][0]=0;
	for(int i=1;i<=x;i++){
		dp[i][0]=cal(dp[i-1][0],dis);
	}
	for(int i=1;i<=y;i++){
		dp[0][i]=cal(dp[0][i-1],2*dis);
	}
	for(int i=1;i<=x;i++){
		for(int j=1;j<=y;j++){
			dp[i][j]=max(cal(dp[i-1][j],dis),cal(dp[i][j-1],2*dis));
		}
	}
	if(dp[x][y]==n){
		return true;
	}
	return false;
}
void solve(){
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		vt.pb(arr[i]);
	}
	sort(all(vt));
	ll l=0,r=1e9,k=0;
	while(l<=r){
		ll m=(l+r)/2;
		if(check(a,b,m)){
			r=m-1;
			k=m;
		}
		else{
			l=m+1;
		}
	}
	cout<<k<<endl;
}
int main(){
	IOS;
	//cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

Compilation message

watching.cpp: In function 'long long int cal(int, long long int)':
watching.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i=ind;i<vt.size();i++){
      |                ~^~~~~~~~~~

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 716 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 460 KB Output is correct
12 Correct 1 ms 460 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 505 ms 23908 KB Output is correct
4 Correct 47 ms 9548 KB Output is correct
5 Correct 42 ms 1612 KB Output is correct
6 Correct 817 ms 31788 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 43 ms 1604 KB Output is correct
9 Correct 46 ms 4044 KB Output is correct
10 Correct 60 ms 9296 KB Output is correct
11 Correct 45 ms 1740 KB Output is correct
12 Correct 247 ms 11832 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 460 KB Output is correct
15 Correct 2 ms 460 KB Output is correct