oj.uz

답안 #100803

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
100803 2019-03-14T14:38:00 Z arman_ferdous 구경하기 (JOI13_watching) C++17
0 / 100
 3 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
int n, p, q, arr[2010];
int cost[2010];

bool can(int w) {
	for(int i = 0; i < n; i++) cost[i] = 1;
	int P = p, Q = q;

	while(Q--) {
		int cur = 0, curcost = 0, optL = 0, optR = 0, mx = -1;
		for(int i = 0; i < n; i++) {
			while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= 2*w) {
				curcost += cost[cur + 1];
				cur++;
			}
			if(curcost > mx) mx = curcost, optL = i, optR = cur;
			curcost -= cost[i];
		}
		for(int i = optL; i <= optR; i++) cost[i] = 0;
	}
	while(P--) {
		int cur = 0, curcost = 0, optL = 0, optR = 0, mx = -1;
		for(int i = 0; i < n; i++) {
			while(cur + 1 < n && arr[cur + 1] - arr[i] + 1 <= w) {
				curcost += cost[cur + 1];
				cur++;
			}
			if(curcost > mx) mx = curcost, optL = i, optR = cur;
			curcost -= cost[i];
		}
		for(int i = optL; i <= optR; i++) cost[i] = 0;
	} 
	int cnt = 0;
	for(int i = 0; i < n; i++) cnt += cost[i];
	return cnt == 0;
}

int main() {
	scanf("%d %d %d", &n, &p, &q);
	for(int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	sort(arr,arr+n);
	if(p + q >= n) {
		puts("1");
		return 0;
	}
	int lo = 1, hi = (int)1e9+10, ans;
	while(lo <= hi) {
		int mid = (lo + hi) >> 1;
		if(can(mid)) hi = mid-1, ans = mid;
		else lo = mid+1;
	} printf("%d", ans);
	return 0;
}

Compilation message

watching.cpp: In function 'int main()':
watching.cpp:42: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:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -