Submission #942091

#	Time	Username	Problem	Language	Result	Execution time	Memory
942091		dshfjka	Watching (JOI13_watching)	C++14	100 / 100	274 ms	30300 KiB

watching

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
	LL n,p,q;
	scanf("%lld %lld %lld",&n,&p,&q);
	LL arr[n+5];
	for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
	sort(arr+1,arr+n+1);
	LL left=1,right=1e9,ans=-1;
	LL all=p+q;
	if(p+q>=n)
	{
		printf("1\n");
		exit(0);
	}
	while(left<=right)
	{
		LL mid=(left+right)/2;
	//	printf("mid=%lld\n",mid);
		LL dp[n+5][p+5];
		// now, p , minimum q
		for(LL a=0;a<=n+1;a++)for(LL b=0;b<=p;b++)dp[a][b]=1e9;
		LL lastp=1,lastq=1;
		dp[1][0]=0;
		for(LL a=1;a<=n;a++)
		{
			while(lastp!=n+1 && arr[lastp]-arr[a]+1<=mid)lastp++;
			while(lastq!=n+1 && arr[lastq]-arr[a]+1<=2*mid)lastq++;
			for(LL b=p;b>=0;b--)
			{
			//	printf("%lld %lld\n",a,b);
			//	if(dp[a][b]>=2500)continue;
				dp[lastp][b+1]=min(dp[lastp][b+1],dp[a][b]);
				dp[lastq][b]=min(dp[lastq][b],dp[a][b]+1);
			//	printf("dp[%lld][%lld] = %lld\n",lastp,b+1,dp[lastp][b+1]);
			//	printf("dp[%lld][%lld] = %lld\n",lastq,b,dp[lastq][b]);
			}
		}
		bool bisa=false;
		for(LL b=0;b<=p;b++)
		{
			if(dp[n+1][b]<=q){
				bisa=1;
				break;
			}
		}
		if(bisa){
			ans=mid;
			right=mid-1;
		}
		else left=mid+1;
	}
	printf("%lld\n",ans);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:12:5: warning: unused variable 'all' [-Wunused-variable]
   12 |  LL all=p+q;
      |     ^~~
watching.cpp:7:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |  scanf("%lld %lld %lld",&n,&p,&q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
watching.cpp:9:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  for(LL a=1;a<=n;a++)scanf("%lld",&arr[a]);
      |                      ~~~~~^~~~~~~~~~~~~~~~

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