Submission details
Task:Backup
Sender:ArktinenKarpalo
Submission time:2019-03-07 16:28:30 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#20.01 s1, 2, 3details
#3--3details
#4--3details
#5ACCEPTED0.02 s1, 2, 3details
#60.20 s2, 3details
#7ACCEPTED0.02 s1, 2, 3details
#80.01 s1, 2, 3details
#90.03 s2, 3details
#100.13 s2, 3details
#11--3details
#12--3details
#13ACCEPTED0.27 s3details
#14ACCEPTED0.02 s1, 2, 3details
#150.03 s2, 3details
#16ACCEPTED0.05 s3details
#17--3details
#18ACCEPTED0.03 s2, 3details
#19ACCEPTED0.02 s2, 3details
#20--3details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:58:8: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
   z[b] = 1;
   ~~~~~^~~
input/code.cpp:57:8: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
   z[a] = 1;
   ~~~~~^~~

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 1000000007
#define P complex<long long>
#define X real()
#define Y imag()
using namespace std;
int n, k, s[101010], z[101010], ss[101010];
ll ans = 1e14;
vector<pair<int,int>> v;
void haku(int otettu, int nyk, ll sum) {
if(otettu == k)
ans=min(sum,ans);
if(nyk >= n-1 || otettu == k)
return;
haku(otettu, nyk+1, sum);
haku(otettu+1, nyk+2, sum+ss[nyk]);
}
int main() {
cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);
cin >> n >> k;
for(int i=0; i<n; i++) {
cin >> s[i];
if(i)
ss[i-1] = s[i]-s[i-1];
}
// haku(0,0,0);
//cout << ans << " ";
ans = 1e14;
for(int i=0; i<k; i++) {
int mini = 1e9+1;
int a, b, oik=0;
for(int j=0; j<n-1; j++) {
if(z[j])
continue;
oik = j+1;
while(z[oik]) {
oik++;
}
if(oik == n)
continue;
if(s[oik]-s[j] <= mini) {
a = j;
b = oik;
mini = s[oik]-s[j];
}
}
z[a] = 1;
z[b] = 1;
}
ans = 0;
int ed = -1;
for(int i=0; i<n; i++) {
if(z[i]) {
if(ed == -1) {
ed = i;
} else {
ans += s[i]-s[ed];
ed = -1;
}
}
}
// haku(0,0,0);
cout << ans;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
2 1
0
1000000000

correct output
1000000000

user output
1000000000

Test 2

Group: 1, 2, 3

Verdict:

input
17 8
101266
101394
101458
101490
...

correct output
340

user output
425

Test 3

Group: 3

Verdict:

input
100000 49000
29983
53806
76909
106815
...

correct output
411321413

user output
(empty)

Test 4

Group: 3

Verdict:

input
100000 30000
29983
53806
76909
106815
...

correct output
100755932

user output
(empty)

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
20 10
126229031
250138471
333910089
443521720
...

correct output
537092323

user output
537092323

Test 6

Group: 2, 3

Verdict:

input
10000 4999
168328
266967
462469
639689
...

correct output
492516409

user output
494438934

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
10 4
165
375
439
456
...

correct output
44

user output
44

Test 8

Group: 1, 2, 3

Verdict:

input
20 9
4336
4500
4552
4702
...

correct output
773

user output
776

Test 9

Group: 2, 3

Verdict:

input
2001 1000
1230
1440
1630
2230
...

correct output
493503

user output
493701

Test 10

Group: 2, 3

Verdict:

input
10000 3000
245408
417449
650973
863296
...

correct output
101056127

user output
101992308

Test 11

Group: 3

Verdict:

input
50000 20000
37035
37042
37046
37052
...

correct output
129968

user output
(empty)

Test 12

Group: 3

Verdict:

input
99999 48000
15929
43928
65765
86730
...

correct output
375524431

user output
(empty)

Test 13

Group: 3

Verdict: ACCEPTED

input
100000 1000
536
9214
34619
53734
...

correct output
75975

user output
75975

Test 14

Group: 1, 2, 3

Verdict: ACCEPTED

input
10 4
5851
5854
5856
5859
...

correct output
2664

user output
2664

Test 15

Group: 2, 3

Verdict:

input
100 45
3712
13742
17394
19428
...

correct output
140256

user output
164410

Test 16

Group: 3

Verdict: ACCEPTED

input
20000 400
3174
3175
3176
3179
...

correct output
803105

user output
803105

Test 17

Group: 3

Verdict:

input
100000 49000
3605
14510
18001
20881
...

correct output
162316123

user output
(empty)

Test 18

Group: 2, 3

Verdict: ACCEPTED

input
100 50
0
1000000
1000002
1000005
...

correct output
1002499

user output
1002499

Test 19

Group: 2, 3

Verdict: ACCEPTED

input
1000 500
0
1000000
1000002
1000005
...

correct output
1249999

user output
1249999

Test 20

Group: 3

Verdict:

input
100000 49494
123
65659
98427
114811
...

correct output
250954854

user output
(empty)