Submission #371278

#	Time	Username	Problem	Language	Result	Execution time	Memory
371278		peijar	Watching (JOI13_watching)	C++17	100 / 100	489 ms	16484 KiB

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 / 50
• Subtask 2: 50 / 50