oj.uz

Submission #241045

# Submission time Handle Problem Language Result Execution time Memory
241045 2020-06-22T11:07:08 Z computerbox Watching (JOI13_watching) C++14
100 / 100
 323 ms 32120 KB 
#include <bits/stdc++.h>
#define FLASH ios_base::sync_with_stdio(0);
#define ll long long
#define debt(x,y)cout<<"#x = "<<(x)<<" and "<<"#y = "<<(y)<<endl;
#define deb(x)cout<<"#x = "<<(x)<<endl;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define endl "\n"
#define arr(a,n) for(ll i=1;i<=n;i++) cout<<a[i]<<" "; cout << "\n";
#define vecc(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout << "\n";


using namespace std;

ll dp[2010][2010];
vector<ll>massiv;
ll n,p,q;

ll f(ll w)
{
  memset(dp,0,sizeof(dp));
  ll pointbig=0;
  ll pointsmall=0;
  for(ll i=0;i<n;i++)
  {
	while(pointsmall<n && massiv[i]-massiv[pointsmall]>=w)pointsmall++;
	while(pointbig<n && massiv[i]-massiv[pointbig]>=2*w)pointbig++; 
	for(ll j=0;j<=min(q,n);j++)
	{
	  if(j==0)
	  {
		if(pointsmall==0)dp[i][j]=1;  
		else dp[i][j]=dp[pointsmall-1][j]+1;
	  }
	  else
	  {
	   if(pointbig==0)dp[i][j]=0;
	   else if(pointsmall==0)dp[i][j]=min(dp[pointbig-1][j-1],1LL);
	   else dp[i][j]=min(dp[pointsmall-1][j]+1,dp[pointbig-1][j-1]); 	
	  } 
    } 
  }
  ll minn=LLONG_MAX;
  
  
  for(ll i=0;i<=min(q,n);i++)minn=min(minn,dp[n-1][i]);
  if(minn<=p)return 1;
  else return 0;	
}


int main(){
FLASH;
cin>>n>>p>>q;
for(ll i=1;i<=n;i++){ll x;cin>>x;massiv.pb(x);}

sort(all(massiv));
ll nac=0;
ll konec=massiv.back()+10;
ll minn=LONG_MAX;
while(nac+1<konec)
{
  ll mid=nac+(konec-nac)/2;
  ll check=f(mid);
  if(check==1){minn=min(minn,mid);konec=mid;}
  else nac=mid;	
}

cout<<minn<<endl;




return 0;
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 32120 KB Output is correct
2 Correct 123 ms 32000 KB Output is correct
3 Correct 132 ms 32000 KB Output is correct
4 Correct 123 ms 32008 KB Output is correct
5 Correct 127 ms 32000 KB Output is correct
6 Correct 123 ms 32000 KB Output is correct
7 Correct 127 ms 32000 KB Output is correct
8 Correct 128 ms 32000 KB Output is correct
9 Correct 129 ms 32120 KB Output is correct
10 Correct 124 ms 32000 KB Output is correct
11 Correct 130 ms 32000 KB Output is correct
12 Correct 131 ms 32120 KB Output is correct
13 Correct 127 ms 32000 KB Output is correct
14 Correct 117 ms 32000 KB Output is correct
15 Correct 125 ms 32000 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 32000 KB Output is correct
2 Correct 118 ms 32000 KB Output is correct
3 Correct 259 ms 32000 KB Output is correct
4 Correct 138 ms 32000 KB Output is correct
5 Correct 290 ms 32120 KB Output is correct
6 Correct 293 ms 32000 KB Output is correct
7 Correct 140 ms 32000 KB Output is correct
8 Correct 209 ms 32120 KB Output is correct
9 Correct 152 ms 32000 KB Output is correct
10 Correct 148 ms 32088 KB Output is correct
11 Correct 323 ms 32120 KB Output is correct
12 Correct 225 ms 32120 KB Output is correct
13 Correct 134 ms 32000 KB Output is correct
14 Correct 132 ms 31992 KB Output is correct
15 Correct 147 ms 32080 KB Output is correct