oj.uz

답안 #1106620

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106620 2024-10-30T17:43:47 Z xnqs 구경하기 (JOI13_watching) C++17
100 / 100
 570 ms 16376 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <cstring>

int x, p, q;
std::vector<int> arr;
int dp[2001][2001];
int next[2][2001];

int solve(int pos, int k) {
	if (k>q) {
		return 0x3f3f3f3f;
	}
	if (pos==x) {
		return 0;
	}
	if (dp[pos][k]!=-1) {
		return dp[pos][k];
	}

	int ret = solve(next[1][pos],k+1);
	for (int i = pos; i < next[0][pos]; i++) {
		ret = std::min(ret, 1 + solve(i+1,k));
	}

	return dp[pos][k] = ret;
}

bool can_solve(int cap) {
	for (int i = 0; i < 2; i++) {
		for (int l = x-1, r = x-1; l >= 0; l--) {
			while (arr[r]-arr[l]+1>(i+1)*cap) {
				--r;
			}

			next[i][l] = r+1;
		}
	}

	memset(dp,-1,sizeof(dp));
	return solve(0,0) <= p;
}
 
int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
 
	std::cin >> x >> p >> q;
 
	// we only need at most x cameras in total, out of which we'll greedily take as many big cameras as possible
	if (p+q>x) {
		q = std::min(q, x);
		p = x-q;
	}
 
	for (int i = 0, tmp; i < x; i++) {
		std::cin >> tmp;
		arr.emplace_back(tmp);
	}
 
	std::sort(arr.begin(),arr.end());
	const auto bs = [&]() {
		int ret = 1000000001;
		int l = 1, r = 1000000000;
		while (l<=r) {
			int m = (l+r)>>1;
			if (can_solve(m)) {
				ret = m;
				r = m-1;
			}
			else {
				l = m+1;
			}
		}
		return ret;
	};
 
	std::cout << bs() << "\n";
	//can_solve(bs(),1);
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 15952 KB Output is correct
2 Correct 11 ms 16128 KB Output is correct
3 Correct 12 ms 16120 KB Output is correct
4 Correct 14 ms 15952 KB Output is correct
5 Correct 12 ms 16140 KB Output is correct
6 Correct 13 ms 15952 KB Output is correct
7 Correct 12 ms 15952 KB Output is correct
8 Correct 13 ms 15952 KB Output is correct
9 Correct 12 ms 15952 KB Output is correct
10 Correct 12 ms 15952 KB Output is correct
11 Correct 12 ms 16104 KB Output is correct
12 Correct 13 ms 15952 KB Output is correct
13 Correct 11 ms 15952 KB Output is correct
14 Correct 12 ms 15952 KB Output is correct
15 Correct 13 ms 15952 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 16208 KB Output is correct
2 Correct 14 ms 15952 KB Output is correct
3 Correct 472 ms 16208 KB Output is correct
4 Correct 194 ms 16208 KB Output is correct
5 Correct 406 ms 16208 KB Output is correct
6 Correct 421 ms 16296 KB Output is correct
7 Correct 188 ms 16300 KB Output is correct
8 Correct 570 ms 16324 KB Output is correct
9 Correct 235 ms 16208 KB Output is correct
10 Correct 138 ms 16376 KB Output is correct
11 Correct 388 ms 16208 KB Output is correct
12 Correct 340 ms 16208 KB Output is correct
13 Correct 132 ms 16320 KB Output is correct
14 Correct 110 ms 16376 KB Output is correct
15 Correct 112 ms 16208 KB Output is correct