CSES - Datatähti Open 2021 - Results
Submission details
Task:Programmers
Sender:tutis
Submission time:2021-01-30 20:35:52 +0200
Language:C++11
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED34
#2ACCEPTED21
#3ACCEPTED45
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s1, 2, 3details
#3ACCEPTED0.01 s1, 2, 3details
#4ACCEPTED0.01 s1, 2, 3details
#5ACCEPTED0.01 s1, 2, 3details
#6ACCEPTED0.01 s1, 2, 3details
#7ACCEPTED0.01 s1, 2, 3details
#8ACCEPTED0.01 s1, 2, 3details
#9ACCEPTED0.01 s1, 2, 3details
#10ACCEPTED0.01 s1, 2, 3details
#11ACCEPTED0.01 s1, 2, 3details
#12ACCEPTED0.01 s1, 3details
#13ACCEPTED0.01 s1, 3details
#14ACCEPTED0.01 s1, 3details
#15ACCEPTED0.01 s1, 3details
#16ACCEPTED0.01 s1, 3details
#17ACCEPTED0.12 s2, 3details
#18ACCEPTED0.38 s2, 3details
#19ACCEPTED0.38 s2, 3details
#20ACCEPTED0.38 s2, 3details
#21ACCEPTED0.38 s2, 3details
#22ACCEPTED0.38 s2, 3details
#23ACCEPTED0.38 s2, 3details
#24ACCEPTED0.52 s3details
#25ACCEPTED0.53 s3details
#26ACCEPTED0.53 s3details
#27ACCEPTED0.53 s3details
#28ACCEPTED0.53 s3details
#29ACCEPTED0.54 s3details
#30ACCEPTED0.53 s3details
#31ACCEPTED0.53 s3details

Compiler report

input/code.cpp: In function 'std::vector<int> suma(const std::vector<int>&, const std::vector<int>&)':
input/code.cpp:30:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int ij = 0; ij < ret.size(); ij++)
                   ~~~^~~~~~~~~~~~
input/code.cpp: In lambda function:
input/code.cpp:86:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
        for (int i = 0; i < vec.size(); i++)
                        ~~^~~~~~~~~~~~
input/code.cpp:92:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < vec.size(); i++)
                         ~~^~~~~~~~~~~~

Code

/*input
8 3
3 1 2 7 9 3 4 7
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using ordered_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using fast_map = cc_hash_table<T, X>;
//using ull = __uint128_t;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
mt19937_64 rng(123);
const ll mod = 1000000007;
const int inf = 1000000000;
vector<int>suma(const vector<int>&a, const vector<int>&b)
{
	if (a.empty() || b.empty())
		return {};
	vector<int>ret(a.size() + b.size() - 1, inf);
	int i = 0;
	for (int ij = 0; ij < ret.size(); ij++)
	{
		//ij>=i
		//
		//ij-b.size()+1<=i
		int mn = max(0, ij - (int)b.size() + 1);
		int mx = min((int)a.size() - 1, ij);
		i = max(i, mn);
		i = min(i, mx);
		while (true)
		{
			if (i - 1 >= mn && a[i - 1] + b[ij - (i - 1)] < a[i] + b[ij - i])
				i--;
			else if (i + 1 <= mx && a[i + 1] + b[ij - (i + 1)] < a[i] + b[ij - i])
				i++;
			else
				break;
		}
		ret[ij] = a[i] + b[ij - i];
	}
	return ret;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> A(n);
	for (int i = 0; i < n; i++)
		cin >> A[i];
	sort(A.begin(), A.end());
	function<array<array<vector<int>, 2>, 2>(int, int)>dp = [&](int l, int r)
	{
		array<array<vector<int>, 2>, 2>ret;
		if (l == r)
		{
			ret[1][0].push_back(0);
			ret[0][1].push_back(0);
			ret[1][1].push_back(0);
		}
		else
		{
			array<array<vector<int>, 2>, 2>a = dp(l, (l + r) / 2);
			array<array<vector<int>, 2>, 2>b = dp((l + r) / 2 + 1, r);
			int gal = A[(l + r) / 2 + 1] - A[(l + r) / 2];
			for (int x = 0; x < 2; x++)
				for (int t = 0; t < 2; t++)
				{
					for (int y = 0; y < 2; y++)
						for (int z = 0; z < 2; z++)
						{
							vector<int>vec = suma(a[x][y], b[z][t]);
							while (ret[x][t].size() < vec.size())
								ret[x][t].push_back(inf);
							for (int i = 0; i < vec.size(); i++)
								ret[x][t][i] = min(ret[x][t][i], vec[i]);
							if (y == 0 && z == 0)
							{
								while (ret[x][t].size() < vec.size() + 1)
									ret[x][t].push_back(inf);
								for (int i = 0; i < vec.size(); i++)
								{
									ret[x][t][i + 1] = min(ret[x][t][i + 1], vec[i] + gal);
								}
							}
						}
				}
		}
		return ret;
	};
	cout << dp(0, n - 1)[1][1][k] << "\n";
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
8 3
3 1 2 7 9 3 4 7

correct output
1

user output
1

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
2 1
2 13

correct output
11

user output
11

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
20 10
16 20 6 15 19 12 11 17 20 6 15...

correct output
6

user output
6

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
14 5
11 3 8 3 14 8 10 13 11 10 17 1...

correct output
0

user output
0

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
15 1
8 5 1 8 18 15 6 20 14 9 10 9 1...

correct output
0

user output
0

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
10 3
10 19 16 15 12 5 14 8 3 15

correct output
4

user output
4

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
202 90
177 187 183 647 616 580 499 78...

correct output
213

user output
213

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 512
141 583 135 833 900 308 248 58...

correct output
0

user output
0

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 972
685 4 289 865 93 159 48 866 56...

correct output
276

user output
276

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 1000
698 153 298 118 631 341 238 7 ...

correct output
517

user output
517

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
2000 1
983 144 449 584 839 166 77 885...

correct output
0

user output
0

Test 12

Group: 1, 3

Verdict: ACCEPTED

input
1464 320
846762124 954854396 12767390 7...

correct output
35809369

user output
35809369

Test 13

Group: 1, 3

Verdict: ACCEPTED

input
2000 231
801945178 924940258 369188694 ...

correct output
7831421

user output
7831421

Test 14

Group: 1, 3

Verdict: ACCEPTED

input
2000 461
464790475 932031556 838378103 ...

correct output
37272564

user output
37272564

Test 15

Group: 1, 3

Verdict: ACCEPTED

input
2000 100
484046702 267135814 995006323 ...

correct output
1268400

user output
1268400

Test 16

Group: 1, 3

Verdict: ACCEPTED

input
2000 996
98352148 438929491 242618159 1...

correct output
445965905

user output
445965905

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
65879 19675
896 316 972 476 636 227 716 78...

correct output
0

user output
0

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
200000 53820
995 720 135 767 943 742 191 26...

correct output
0

user output
0

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
200000 32297
527 947 84 851 908 833 339 112...

correct output
0

user output
0

Test 20

Group: 2, 3

Verdict: ACCEPTED

input
200000 99982
561 174 242 275 460 109 664 68...

correct output
322

user output
322

Test 21

Group: 2, 3

Verdict: ACCEPTED

input
200000 99955
911 33 314 861 298 117 972 982...

correct output
245

user output
245

Test 22

Group: 2, 3

Verdict: ACCEPTED

input
200000 99972
783 1000 673 611 87 452 702 92...

correct output
290

user output
290

Test 23

Group: 2, 3

Verdict: ACCEPTED

input
200000 99961
795 136 128 643 60 422 371 839...

correct output
252

user output
252

Test 24

Group: 3

Verdict: ACCEPTED

input
195426 76599
442872072 619088799 118541378 ...

correct output
143376538

user output
143376538

Test 25

Group: 3

Verdict: ACCEPTED

input
200000 1661
894106972 620084612 931442312 ...

correct output
33089

user output
33089

Test 26

Group: 3

Verdict: ACCEPTED

input
200000 86032
211444153 846442677 297198384 ...

correct output
196001810

user output
196001810

Test 27

Group: 3

Verdict: ACCEPTED

input
200000 28275
28280312 349705372 96535649 84...

correct output
11627219

user output
11627219

Test 28

Group: 3

Verdict: ACCEPTED

input
200000 81473
178022892 112774306 250584651 ...

correct output
162430841

user output
162430841

Test 29

Group: 3

Verdict: ACCEPTED

input
200000 99987
297598052 494409138 182268523 ...

correct output
489497036

user output
489497036

Test 30

Group: 3

Verdict: ACCEPTED

input
200000 99971
316462272 843156468 434342923 ...

correct output
483167476

user output
483167476

Test 31

Group: 3

Verdict: ACCEPTED

input
200000 99964
811543559 465033274 620180191 ...

correct output
481497328

user output
481497328