답안 #371278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371278	2021-02-26T10:42:30 Z	peijar	구경하기 (JOI13_watching)	C++17	100 / 100	489 ms	16484 KB

watching

#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)
	{
		int iPosPetite = 
			lower_bound(posPhotos.begin(), posPhotos.begin()+nbVoulus, posPhotos[nbVoulus-1] - w+1) - posPhotos.begin();
			int iPosGrande = 
				lower_bound(posPhotos.begin(), posPhotos.begin() + nbVoulus, posPhotos[nbVoulus-1]-2*w+1) - posPhotos.begin();
		for (int petits(0); petits <= nbPetites; ++petits)
		{
			if (petits > 0)
			{
				minNecessaire[nbVoulus][petits] = 
					min(minNecessaire[nbVoulus][petits], 
							minNecessaire[iPosPetite][petits-1]);
			}
			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	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 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

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	492 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	370 ms	12292 KB	Output is correct
4	Correct	485 ms	16364 KB	Output is correct
5	Correct	23 ms	1084 KB	Output is correct
6	Correct	489 ms	16484 KB	Output is correct
7	Correct	10 ms	620 KB	Output is correct
8	Correct	34 ms	1468 KB	Output is correct
9	Correct	183 ms	6436 KB	Output is correct
10	Correct	461 ms	15440 KB	Output is correct
11	Correct	25 ms	1180 KB	Output is correct
12	Correct	235 ms	8324 KB	Output is correct
13	Correct	8 ms	492 KB	Output is correct
14	Correct	9 ms	620 KB	Output is correct
15	Correct	8 ms	620 KB	Output is correct