oj.uz

답안 #371276

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
371276 2021-02-26T10:39:26 Z peijar 구경하기 (JOI13_watching) C++17
50 / 100
 1000 ms 12316 KB 
#include <bits/stdc++.h>
#define SZ(v) ((int)(v).size())
using namespace std;

using ll = long long;

template<typename... Args>
void read(Args&... args)
{
	((cin >> args), ...);
}
template<typename T>
void read(vector<T> &vec)
{
	for (auto &v : vec) read(v);
}

void write() {}
template<typename H, typename... T>
void write(const H &h, const T&... t)
{
	cout << h;
	if (sizeof...(t)) {cout << ' '; write(t...);}
}

template<typename T>
void write(const vector<T> &vec)
{
	if (SZ(vec) == 0) return;
	write(vec[0]);
	for (int i(1); i < SZ(vec); ++i)
	{cout << ' '; write(vec[i]);}
}

template<typename... Args>
void writeln(Args... args)
{
	write(args...); cout << '\n';
}

const int MAXLEN = 1e9;

int nbPhotos;
vector<int> posPhotos;
int nbPetites, nbGrosses;

bool can(int w)
{
	vector<vector<int>> minNecessaire(nbPhotos+1, vector<int>(nbPetites+1, 1e9));
	for (int p(0); p <= nbPetites; ++p)
		minNecessaire[0][p] = 0;
	for (int nbVoulus(1); nbVoulus <= nbPhotos; ++nbVoulus)
		for (int petits(0); petits <= nbPetites; ++petits)
		{
			if (petits > 0)
			{
				int iPosPetite = 
					lower_bound(posPhotos.begin(), posPhotos.begin()+nbVoulus, posPhotos[nbVoulus-1] - w+1) - posPhotos.begin();
				minNecessaire[nbVoulus][petits] = 
					min(minNecessaire[nbVoulus][petits], 
							minNecessaire[iPosPetite][petits-1]);
			}
			int iPosGrande = 
				lower_bound(posPhotos.begin(), posPhotos.begin() + nbVoulus, posPhotos[nbVoulus-1]-2*w+1) - posPhotos.begin();
			minNecessaire[nbVoulus][petits] = 
				min(minNecessaire[nbVoulus][petits],
						1 + minNecessaire[iPosGrande][petits]);
		}
	return minNecessaire[nbPhotos][nbPetites] <= nbGrosses;
}

int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	read(nbPhotos, nbPetites, nbGrosses);
	nbPetites = min(nbPetites, nbPhotos);
	posPhotos.resize(nbPhotos);
	read(posPhotos);
	sort(posPhotos.begin(), posPhotos.end());
	int lo(1), up(MAXLEN);
	while (lo < up)
	{
		int mid = (lo + up) / 2;
		if (can(mid))
			up = mid;
		else
			lo = mid+1;
	}
	writeln(lo);
}

Subtask #1
50.0 / 50.0

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

Subtask #2
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 492 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Execution timed out 1092 ms 12316 KB Time limit exceeded
4 Halted 0 ms 0 KB -