280072026-05-14 10:27:44PappMatyasSakk párosításokcpp17Időlimit túllépés 5/1001.6s6704 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

struct ll2
{
	ll a;
	ll b;
};

static bool Compare(ll2 a, ll2 b)
{
	return a.a < b.a;
}

int main()
{
	int n, m;
	cin >> n >> m;

	vector<ll> v(n);
	vector<ll> dif(n - 1);
	vector<ll2> difs(n - 1);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	sort(v.begin(), v.end());

	for (int i = 0; i < n - 1; i++)
	{
		dif[i] = v[i + 1] - v[i];
		difs[i].a = v[i + 1] - v[i];
		difs[i].b = i;
	}

	sort(difs.begin(), difs.end(), Compare);

	ll ans = 0;
	int pos = 0;
	vector<int> deleted;
	for (int c = 0; c < m; c++)
	{
		if (difs[pos].a == dif[difs[pos].b])
		{
			ans += difs[pos].a;
			ll adder = 0;
			adder += dif[difs[pos].b];
			dif[difs[pos].b] = -1;
			deleted.push_back(difs[pos].b);
			if (difs[pos].b + 1 < dif.size())
			{
				adder += dif[difs[pos].b + 1];
				dif[difs[pos].b + 1] = -1;
				deleted.push_back(difs[pos].b + 1);
			}
			if (difs[pos].b - 1 >= 0)
			{
				dif[difs[pos].b - 1] += adder;
			}
			pos++;
			continue;
		}
		else
		{
			sort(deleted.begin(), deleted.end());
			for (int i = 0; i < deleted.size(); i++)
			{
				dif.erase(dif.begin() + deleted[i] - i);
			}
			for (int i = 0; i < dif.size(); i++)
			{
				difs[i].a = dif[i];
				difs[i].b = i;
			}
			sort(difs.begin(), difs.end(), Compare);
			deleted.clear();

			pos = 0;
			ans += difs[pos].a;
			ll adder = 0;
			adder += dif[difs[pos].b];
			dif[difs[pos].b] = -1;
			deleted.push_back(difs[pos].b);
			if (difs[pos].b + 1 < dif.size())
			{
				adder += dif[difs[pos].b + 1];
				dif[difs[pos].b + 1] = -1;
				deleted.push_back(difs[pos].b + 1);
			}
			if (difs[pos].b - 1 >= 0)
			{
				dif[difs[pos].b - 1] += adder;
			}
			pos++;
		}
	}
	cout << ans;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask25/5
3Elfogadva138ms6432 KiB
4Elfogadva140ms6452 KiB
5Elfogadva138ms6672 KiB
6Elfogadva140ms6672 KiB
7Elfogadva141ms6472 KiB
subtask30/11
8Időlimit túllépés1.585s6680 KiB
9Időlimit túllépés1.585s6556 KiB
10Időlimit túllépés1.585s6472 KiB
11Időlimit túllépés1.585s6636 KiB
12Időlimit túllépés1.588s6680 KiB
13Időlimit túllépés1.588s6676 KiB
14Időlimit túllépés1.588s6632 KiB
15Időlimit túllépés1.588s6672 KiB
16Időlimit túllépés1.588s6676 KiB
17Időlimit túllépés1.588s6452 KiB
18Időlimit túllépés1.59s6644 KiB
subtask40/14
19Elfogadva2ms316 KiB
20Elfogadva1ms316 KiB
21Elfogadva1ms316 KiB
22Elfogadva1ms500 KiB
23Elfogadva1ms384 KiB
24Elfogadva1ms316 KiB
25Hibás válasz1ms316 KiB
26Futási hiba1ms316 KiB
27Hibás válasz1ms316 KiB
28Hibás válasz1ms512 KiB
29Hibás válasz1ms316 KiB
30Hibás válasz1ms352 KiB
31Hibás válasz1ms316 KiB
32Hibás válasz1ms508 KiB
33Elfogadva1ms316 KiB
34Elfogadva1ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva2ms500 KiB
39Elfogadva1ms316 KiB
40Hibás válasz1ms316 KiB
41Elfogadva1ms500 KiB
42Hibás válasz1ms316 KiB
43Futási hiba1ms316 KiB
44Hibás válasz1ms316 KiB
45Elfogadva2ms316 KiB
46Hibás válasz1ms316 KiB
47Elfogadva1ms316 KiB
48Elfogadva1ms316 KiB
49Hibás válasz2ms316 KiB
50Elfogadva1ms316 KiB
51Elfogadva1ms316 KiB
52Elfogadva1ms316 KiB
53Hibás válasz1ms316 KiB
54Hibás válasz1ms316 KiB
subtask50/21
55Elfogadva2ms316 KiB
56Elfogadva1ms316 KiB
57Elfogadva1ms316 KiB
58Elfogadva1ms500 KiB
59Elfogadva1ms384 KiB
60Elfogadva1ms316 KiB
61Hibás válasz1ms316 KiB
62Futási hiba1ms316 KiB
63Hibás válasz1ms316 KiB
64Hibás válasz1ms512 KiB
65Hibás válasz1ms316 KiB
66Hibás válasz1ms352 KiB
67Hibás válasz1ms316 KiB
68Hibás válasz1ms508 KiB
69Elfogadva1ms316 KiB
70Elfogadva1ms316 KiB
71Elfogadva1ms316 KiB
72Elfogadva1ms316 KiB
73Elfogadva1ms316 KiB
74Elfogadva2ms500 KiB
75Elfogadva1ms316 KiB
76Hibás válasz1ms316 KiB
77Elfogadva1ms500 KiB
78Hibás válasz1ms316 KiB
79Futási hiba1ms316 KiB
80Hibás válasz1ms316 KiB
81Elfogadva2ms316 KiB
82Hibás válasz1ms316 KiB
83Elfogadva1ms316 KiB
84Elfogadva1ms316 KiB
85Hibás válasz2ms316 KiB
86Elfogadva1ms316 KiB
87Elfogadva1ms316 KiB
88Elfogadva1ms316 KiB
89Hibás válasz1ms316 KiB
90Hibás válasz1ms316 KiB
91Elfogadva2ms512 KiB
92Elfogadva2ms316 KiB
93Elfogadva2ms460 KiB
94Elfogadva2ms316 KiB
95Hibás válasz13ms460 KiB
96Hibás válasz10ms508 KiB
97Hibás válasz10ms492 KiB
98Hibás válasz12ms468 KiB
99Hibás válasz14ms468 KiB
100Hibás válasz13ms316 KiB
101Hibás válasz14ms464 KiB
102Hibás válasz13ms464 KiB
103Hibás válasz8ms464 KiB
104Hibás válasz6ms508 KiB
105Hibás válasz6ms316 KiB
106Hibás válasz6ms316 KiB
107Hibás válasz4ms316 KiB
108Hibás válasz6ms472 KiB
109Hibás válasz4ms508 KiB
110Hibás válasz4ms316 KiB
111Hibás válasz4ms696 KiB
112Elfogadva2ms500 KiB
113Hibás válasz6ms460 KiB
114Hibás válasz4ms456 KiB
115Hibás válasz4ms500 KiB
116Hibás válasz3ms316 KiB
117Futási hiba71ms316 KiB
118Hibás válasz64ms460 KiB
119Elfogadva68ms456 KiB
120Hibás válasz63ms456 KiB
121Hibás válasz2ms316 KiB
122Elfogadva9ms460 KiB
123Hibás válasz17ms464 KiB
124Hibás válasz19ms460 KiB
125Elfogadva2ms464 KiB
126Hibás válasz3ms316 KiB
127Hibás válasz3ms508 KiB
128Hibás válasz4ms316 KiB
129Elfogadva3ms316 KiB
130Hibás válasz14ms468 KiB
subtask60/49
131Elfogadva2ms316 KiB
132Elfogadva1ms316 KiB
133Elfogadva138ms6432 KiB
134Elfogadva140ms6452 KiB
135Elfogadva138ms6672 KiB
136Elfogadva140ms6672 KiB
137Elfogadva141ms6472 KiB
138Időlimit túllépés1.585s6680 KiB
139Időlimit túllépés1.585s6556 KiB
140Időlimit túllépés1.585s6472 KiB
141Időlimit túllépés1.585s6636 KiB
142Időlimit túllépés1.588s6680 KiB
143Időlimit túllépés1.588s6676 KiB
144Időlimit túllépés1.588s6632 KiB
145Időlimit túllépés1.588s6672 KiB
146Időlimit túllépés1.588s6676 KiB
147Időlimit túllépés1.588s6452 KiB
148Időlimit túllépés1.59s6644 KiB
149Elfogadva1ms316 KiB
150Elfogadva1ms500 KiB
151Elfogadva1ms384 KiB
152Elfogadva1ms316 KiB
153Hibás válasz1ms316 KiB
154Futási hiba1ms316 KiB
155Hibás válasz1ms316 KiB
156Hibás válasz1ms512 KiB
157Hibás válasz1ms316 KiB
158Hibás válasz1ms352 KiB
159Hibás válasz1ms316 KiB
160Hibás válasz1ms508 KiB
161Elfogadva1ms316 KiB
162Elfogadva1ms316 KiB
163Elfogadva1ms316 KiB
164Elfogadva1ms316 KiB
165Elfogadva1ms316 KiB
166Elfogadva2ms500 KiB
167Elfogadva1ms316 KiB
168Hibás válasz1ms316 KiB
169Elfogadva1ms500 KiB
170Hibás válasz1ms316 KiB
171Futási hiba1ms316 KiB
172Hibás válasz1ms316 KiB
173Elfogadva2ms316 KiB
174Hibás válasz1ms316 KiB
175Elfogadva1ms316 KiB
176Elfogadva1ms316 KiB
177Hibás válasz2ms316 KiB
178Elfogadva1ms316 KiB
179Elfogadva1ms316 KiB
180Elfogadva1ms316 KiB
181Hibás válasz1ms316 KiB
182Hibás válasz1ms316 KiB
183Elfogadva2ms512 KiB
184Elfogadva2ms316 KiB
185Elfogadva2ms460 KiB
186Elfogadva2ms316 KiB
187Hibás válasz13ms460 KiB
188Hibás válasz10ms508 KiB
189Hibás válasz10ms492 KiB
190Hibás válasz12ms468 KiB
191Hibás válasz14ms468 KiB
192Hibás válasz13ms316 KiB
193Hibás válasz14ms464 KiB
194Hibás válasz13ms464 KiB
195Hibás válasz8ms464 KiB
196Hibás válasz6ms508 KiB
197Hibás válasz6ms316 KiB
198Hibás válasz6ms316 KiB
199Hibás válasz4ms316 KiB
200Hibás válasz6ms472 KiB
201Hibás válasz4ms508 KiB
202Hibás válasz4ms316 KiB
203Hibás válasz4ms696 KiB
204Elfogadva2ms500 KiB
205Hibás válasz6ms460 KiB
206Hibás válasz4ms456 KiB
207Hibás válasz4ms500 KiB
208Hibás válasz3ms316 KiB
209Futási hiba71ms316 KiB
210Hibás válasz64ms460 KiB
211Elfogadva68ms456 KiB
212Hibás válasz63ms456 KiB
213Hibás válasz2ms316 KiB
214Elfogadva9ms460 KiB
215Hibás válasz17ms464 KiB
216Hibás válasz19ms460 KiB
217Elfogadva2ms464 KiB
218Hibás válasz3ms316 KiB
219Hibás válasz3ms508 KiB
220Hibás válasz4ms316 KiB
221Elfogadva3ms316 KiB
222Hibás válasz14ms468 KiB
223Időlimit túllépés1.593s6676 KiB
224Időlimit túllépés1.593s6696 KiB
225Időlimit túllépés1.595s6480 KiB
226Időlimit túllépés1.595s6452 KiB
227Időlimit túllépés1.59s6672 KiB
228Időlimit túllépés1.59s6692 KiB
229Időlimit túllépés1.59s6704 KiB
230Időlimit túllépés1.59s6680 KiB
231Időlimit túllépés1.588s6452 KiB
232Hibás válasz1.437s6532 KiB
233Időlimit túllépés1.588s6456 KiB
234Hibás válasz1.092s6688 KiB
235Időlimit túllépés1.582s6452 KiB
236Időlimit túllépés1.578s6456 KiB
237Időlimit túllépés1.585s6644 KiB
238Időlimit túllépés1.6s6484 KiB
239Időlimit túllépés1.587s6452 KiB
240Időlimit túllépés1.585s6452 KiB
241Időlimit túllépés1.582s6452 KiB
242Időlimit túllépés1.6s6452 KiB
243Időlimit túllépés1.582s2356 KiB
244Időlimit túllépés1.575s6452 KiB
245Időlimit túllépés1.582s6452 KiB
246Időlimit túllépés1.6s6452 KiB
247Időlimit túllépés1.588s6452 KiB
248Időlimit túllépés1.582s6644 KiB
249Időlimit túllépés1.58s6644 KiB
250Időlimit túllépés1.6s6452 KiB
251Elfogadva287ms6688 KiB
252Időlimit túllépés1.59s6672 KiB
253Időlimit túllépés1.585s6452 KiB
254Időlimit túllépés1.585s6680 KiB
255Időlimit túllépés1.588s6648 KiB
256Időlimit túllépés1.582s6672 KiB
257Időlimit túllépés1.582s6452 KiB