Submission #1251839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251839		marda	Watching (JOI13_watching)	C++20	0 / 100	1 ms	324 KiB

watching

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <tuple>

#define endl "\n"
#define int long long int
#define ld long double
#define mp make_pair
#define pb push_back
#define Bound 2e5+1

using namespace std;

bool comp(pair<int, int> a, pair<int, int> b) {
	return a.second < b.second;
}


int32_t main()
{

	int n, p, q;
	cin >> n >> p >> q;

	if (p + q >= n) {
		cout << 0;
		return 0;
	}

	int* a = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(a, a + n);

	vector<pair<int,int>> b(n-1);

	for (int i = 0; i < n - 1; i++) {
		b[i] = mp(a[i + 1] - a[i] + 1,i);
	}

	sort(b.rbegin(), b.rend());

	for (int i = 0; i < p + q - 1; i++) {
		b[i].first = -1;
	}

	sort(b.begin(), b.end(), comp);

	vector<int> measure;

	int size = 0;

	for (int i = 0; i < n - 1; i++) {

		if (b[i].first != -1) size += b[i].first;
		else {
			measure.pb(size);
			size = 0;
		}

	}

	if(size != 0) {
		measure.pb(size);
	}

	sort(measure.rbegin(), measure.rend());

	int w = 0;

	for (int i = 0; i < measure.size(); i++) {

		if (q > 0) {
			w = max(w, (measure[i] + 1) / 2);
			q--;
		}
		else w = max(w, measure[i]);

	}

	cout << w;

	return 0;
}

• Subtask 1: 0 / 50
• Subtask 2: 0 / 50