oj.uz

답안 #85373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
85373 2018-11-19T13:59:42 Z psmao 구경하기 (JOI13_watching) C++14
100 / 100
 419 ms 16932 KB 
#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;
}

Compilation message

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.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 888 KB Output is correct
4 Correct 2 ms 888 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 888 KB Output is correct
7 Correct 2 ms 1196 KB Output is correct
8 Correct 2 ms 1200 KB Output is correct
9 Correct 2 ms 1220 KB Output is correct
10 Correct 3 ms 1220 KB Output is correct
11 Correct 3 ms 1228 KB Output is correct
12 Correct 3 ms 1232 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 3 ms 1240 KB Output is correct
15 Correct 2 ms 1244 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8936 KB Output is correct
2 Correct 2 ms 8936 KB Output is correct
3 Correct 336 ms 16636 KB Output is correct
4 Correct 2 ms 16636 KB Output is correct
5 Correct 2 ms 16636 KB Output is correct
6 Correct 2 ms 16636 KB Output is correct
7 Correct 19 ms 16636 KB Output is correct
8 Correct 42 ms 16636 KB Output is correct
9 Correct 179 ms 16636 KB Output is correct
10 Correct 419 ms 16868 KB Output is correct
11 Correct 35 ms 16868 KB Output is correct
12 Correct 229 ms 16932 KB Output is correct
13 Correct 16 ms 16932 KB Output is correct
14 Correct 17 ms 16932 KB Output is correct
15 Correct 16 ms 16932 KB Output is correct