Submission #151251

#	Time	Username	Problem	Language	Result	Execution time	Memory
151251		TadijaSebez	Watching (JOI13_watching)	C++11	100 / 100	206 ms	16572 KiB

watching

#include <bits/stdc++.h>
using namespace std;
const int N=2050;
const int inf=1e9+7;
int n,p,q;
int dp[N][N],a[N];
void Clear(){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) dp[i][j]=inf;}
void ckmn(int &a, int b){ a=min(a,b);}
bool Check(int w)
{
	int ptr=0,qtr=0;
	Clear();
	dp[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		while(a[i]-a[ptr+1]>=w) ptr++;
		while(a[i]-a[qtr+1]>=2*w) qtr++;
		for(int j=0;j<=i;j++)
		{
			dp[i][j]=dp[ptr][j]+1;
			if(j) ckmn(dp[i][j],dp[qtr][j-1]);
		}
	}
	for(int j=0;j<=min(n,q);j++) if(dp[n][j]<=p) return 1;
	return 0;
}
int main()
{
	scanf("%i %i %i",&n,&p,&q);
	for(int i=1;i<=n;i++) scanf("%i",&a[i]);
	sort(a+1,a+1+n);
	int top=a[n]-a[1]+1,bot=1,mid,ans;
	while(top>=bot)
	{
		mid=top+bot>>1;
		if(Check(mid)) ans=mid,top=mid-1;
		else bot=mid+1;
	}
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:35:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
watching.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&p,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
watching.cpp:30:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i",&a[i]);
                        ~~~~~^~~~~~~~~~~~

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