Submission #371276

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
371276	2021-02-26T10:39:26 Z	peijar	Watching (JOI13_watching)	C++17	50 / 100	1000 ms	12316 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)
		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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-