제출 #85373

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
85373		psmao	구경하기 (JOI13_watching)	C++14	100 / 100	419 ms	16932 KiB

watching

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

#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define pb push_back
#define mp make_pair
const int maxn = 2005;

int n, p, q, a[maxn];
int dp[maxn][maxn], g[maxn], gg[maxn];

bool judge(int x)
{
	fo(i,1,n) fo(j,0,p) dp[i][j] = 1<<30;
	dp[0][0] = 0;
	int l, r, mid, pos;
	fo(i,1,n)
	{
		l = 1; r = i; pos = 0;
		while(l <= r)
		{
			mid = l + r >> 1;
			if(a[i]-x+1<=a[mid]) pos = mid, r = mid - 1;
			else l = mid + 1;
		}
		g[i] = pos;
		l = 1; r = i; pos = 0;
		while(l <= r)
		{
			mid = l + r >> 1;
			if(a[i]-x*2+1<=a[mid]) pos = mid, r = mid - 1;
			else l = mid + 1;
		}
		gg[i] = pos;
	}
	fo(i,1,n) fo(j,0,p)
	{
		if(j) dp[i][j] = min(dp[i][j], dp[g[i]-1][j-1]);
		dp[i][j] = min(dp[i][j], dp[gg[i]-1][j]+1);
	}
	fo(i,0,p) if(dp[n][i]<=q) return true;
	return false;
}

void task1()
{
	if(p >= n || q >= n)
	{
		printf("1");
		return;
	}
	int l, r, mid, ans;
	l = 1; r = 1000000000;
	while(l <= r)
	{
		mid = l + r >> 1;
		if(judge(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d",ans);
}

int main()
{
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	scanf("%d%d%d",&n,&p,&q);
	fo(i,1,n) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	task1();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

watching.cpp: In function 'bool judge(int)':
watching.cpp:23:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = l + r >> 1;
          ~~^~~
watching.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid = l + r >> 1;
          ~~^~~
watching.cpp: In function 'void task1()':
watching.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid = l + r >> 1;
         ~~^~~
watching.cpp: In function 'int main()':
watching.cpp:68: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:69:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fo(i,1,n) scanf("%d",&a[i]);
            ~~~~~^~~~~~~~~~~~

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