Submission #223666

#	Time	Username	Problem	Language	Result	Execution time	Memory
223666		arnold518	Watching (JOI13_watching)	C++14	100 / 100	306 ms	16248 KiB

watching

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int INF = 987654321;

int N, P, Q, A[MAXN+10];
int dp[MAXN+10][MAXN+10];

bool solve(int x)
{
	int i, j;

	for(i=0; i<=N; i++) for(j=0; j<=N; j++) dp[i][j]=INF;
	dp[0][0]=0;
	for(i=1; i<=N; i++)
	{
		int p=upper_bound(A+1, A+N+1, A[i]-x)-A-1, q=upper_bound(A+1, A+N+1, A[i]-2*x)-A-1;
		for(j=0; j<=P; j++)
		{
			if(j) dp[i][j]=min(dp[i][j], dp[p][j-1]);
			dp[i][j]=min(dp[i][j], dp[q][j]+1);
		}
	}
	for(j=0; j<=P; j++) if(dp[N][j]<=Q) return true;
	return false;
}

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &P, &Q);
	for(i=1; i<=N; i++) scanf("%d", &A[i]);
	sort(A+1, A+N+1);
	P=min(P, N); Q=min(Q, N);

	int lo=0, hi=1e9+10;
	while(lo+1<hi)
	{
		int mid=lo+hi>>1;
		if(solve(mid)) hi=mid;
		else lo=mid;
	}
	printf("%d\n", hi);
}

Compilation message (stderr)

watching.cpp: In function 'int main()':
watching.cpp:45:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=lo+hi>>1;
           ~~^~~
watching.cpp:35:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
watching.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &P, &Q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:38:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~

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