CSES - APIO 2014 - Results
Submission details
Task:Split the sequence
Sender:Olli
Submission time:2019-03-24 17:57:13 +0200
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
#60
Test results
testverdicttimegroup
#10.02 s1, 2, 3, 4, 5, 6details
#20.02 s1, 2, 3, 4, 5, 6details
#30.03 s1, 2, 3, 4, 5, 6details
#40.01 s1, 2, 3, 4, 5, 6details
#50.02 s1, 2, 3, 4, 5, 6details
#60.02 s1, 2, 3, 4, 5, 6details
#70.01 s1, 2, 3, 4, 5, 6details
#80.01 s1, 2, 3, 4, 5, 6details
#90.02 s1, 2, 3, 4, 5, 6details
#100.02 s1, 2, 3, 4, 5, 6details
#110.02 s1, 2, 3, 4, 5, 6details
#120.02 s1, 2, 3, 4, 5, 6details
#130.01 s1, 2, 3, 4, 5, 6details
#140.02 s1, 2, 3, 4, 5, 6details
#150.02 s1, 2, 3, 4, 5, 6details
#160.01 s1, 2, 3, 4, 5, 6details
#170.02 s1, 2, 3, 4, 5, 6details
#180.03 s2, 3, 4, 5, 6details
#190.02 s2, 3, 4, 5, 6details
#20--2, 3, 4, 5, 6details
#210.02 s2, 3, 4, 5, 6details
#22--2, 3, 4, 5, 6details
#230.42 s2, 3, 4, 5, 6details
#24--2, 3, 4, 5, 6details
#25--2, 3, 4, 5, 6details
#260.44 s2, 3, 4, 5, 6details
#27--2, 3, 4, 5, 6details
#280.03 s3, 4, 5, 6details
#290.03 s3, 4, 5, 6details
#30--3, 4, 5, 6details
#310.03 s3, 4, 5, 6details
#32--3, 4, 5, 6details
#33--3, 4, 5, 6details
#34--3, 4, 5, 6details
#35--3, 4, 5, 6details
#36--3, 4, 5, 6details
#37--3, 4, 5, 6details
#380.54 s4, 5, 6details
#390.54 s4, 5, 6details
#40--4, 5, 6details
#410.52 s4, 5, 6details
#42--4, 5, 6details
#43--4, 5, 6details
#44--4, 5, 6details
#45--4, 5, 6details
#46--4, 5, 6details
#47--4, 5, 6details
#480.02 s5, 6details
#490.01 s5, 6details
#500.02 s5, 6details
#510.03 s5, 6details
#520.01 s5, 6details
#530.01 s5, 6details
#540.02 s5, 6details
#550.03 s5, 6details
#560.02 s5, 6details
#570.02 s5, 6details
#580.02 s6details
#590.01 s6details
#600.02 s6details
#610.02 s6details
#620.02 s6details
#630.01 s6details
#640.02 s6details
#650.02 s6details
#660.01 s6details
#670.02 s6details

Compiler report

input/code.cpp: In function 'll calc(int, int, int)':
input/code.cpp:15:18: warning: array subscript is above array bounds [-Warray-bounds]
  if(ans[a][b][201] != 0) {
     ~~~~~~~~~~~~~^
input/code.cpp: In function 'int main()':
input/code.cpp:15:18: warning: array subscript is above array bounds [-Warray-bounds]
  if(ans[a][b][201] != 0) {
     ~~~~~~~~~~~~~^

Code

#include <iostream>

using namespace std;

const int N = 1001;

typedef long long ll;

ll t[N];
ll ans[N][N][201];
ll sum[N];

ll calc(int a, int b, int k) {
	if(k == 0) return 0;
	if(ans[a][b][201] != 0) {
		return ans[a][b][201] - 1;
	}
	ll an = 0;
	for(int i = a; i < b; ++i) {
		ll cur = (sum[i] - sum[a-1])*(sum[b] - sum[i]);
		cur += calc(i+1, b, k-1);
		an = max(an, cur);
	}
	ans[a][b][k] = an + 1;
	return an;
}

int main() {
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> t[i];
		sum[i] = sum[i-1] + t[i];
	}

	cout << calc(1, n, k) << "\n";
}

Test details

Test 1

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
7 3
4 1 3 4 0 2 3

correct output
108
1 3 5

user output
108

Test 2

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 2
1 2 3 4 5 6 7 8 9 10

correct output
999
6 8

user output
999

Test 3

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
2 1
0 123

correct output
0
1

user output
0

Test 4

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 5
1 1 1 1 1234 1 1 1 1 1234

correct output
1542524
2 4 5 7 9

user output
1542524

Test 5

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 9
10000 10000 10000 10000 10000 ...

correct output
4500000000
1 2 3 4 5 6 7 8 9

user output
4500000000

Test 6

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 1
0 0 0 0 0 0 0 0 1 1

correct output
1
9

user output
1

Test 7

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 1
1 1 0 0 0 0 0 0 0 0

correct output
1
1

user output
1

Test 8

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 1
0 0 0 0 1 1 0 0 0 0

correct output
1
5

user output
1

Test 9

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 3
0 4 2 2 4 4 3 1 10000 10000

correct output
100400096
5 8 9

user output
100400096

Test 10

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 3
10000 10000 10000 10000 10000 ...

correct output
900320000
2 3 4

user output
900320000

Test 11

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 3
9996 9998 9999 9997 9996 9998 ...

correct output
3698080248
2 5 8

user output
3698080248

Test 12

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 4
10000 10000 10000 10000 10000 ...

correct output
3200320000
2 4 6 8

user output
3200320000

Test 13

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
9 4
10000 1 4 0 2 1 3 2 1

correct output
140072
1 4 6 7

user output
140072

Test 14

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
7 3
1445 914 9661 6869 604 6980 56...

correct output
376041456
3 5 6

user output
376041456

Test 15

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 4
0 1 2 3 4 5 6 7 8 9

correct output
805
5 7 8 9

user output
805

Test 16

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 3
10000 1 9997 1 9999 4 9999 4 9...

correct output
900189994
2 5 7

user output
900189994

Test 17

Group: 1, 2, 3, 4, 5, 6

Verdict:

input
10 4
9999 0 9996 1 9999 0 9997 4 10...

correct output
999919994
2 4 6 8

user output
999919994

Test 18

Group: 2, 3, 4, 5, 6

Verdict:

input
50 3
3 1 2 2 3 2 3 4 1 4 0 4 4 4 0 ...

correct output
1093956
16 33 49

user output
1093956

Test 19

Group: 2, 3, 4, 5, 6

Verdict:

input
50 3
10000 10000 10000 4 0 1 3 3 4 ...

correct output
302460000
1 2 3

user output
302460000

Test 20

Group: 2, 3, 4, 5, 6

Verdict:

input
50 49
10000 9996 10000 9997 9998 999...

correct output
122453454361
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
(empty)

Test 21

Group: 2, 3, 4, 5, 6

Verdict:

input
50 3
9998 9999 10000 9998 9998 1000...

correct output
93663683509
12 25 37

user output
93663683509

Test 22

Group: 2, 3, 4, 5, 6

Verdict:

input
50 10
10000 10000 10000 4 4 1 4 0 0 ...

correct output
1005304678
1 2 3 12 17 25 31 41 48 49

user output
(empty)

Test 23

Group: 2, 3, 4, 5, 6

Verdict:

input
50 7
10000 1 2 0 1 2 1 2 3 4 3 1 0 ...

correct output
933702
1 9 14 20 26 32 42

user output
933702

Test 24

Group: 2, 3, 4, 5, 6

Verdict:

input
50 25
8300 1781 4510 1499 3323 5656 ...

correct output
25082842857
1 4 6 7 9 13 14 15 16 17 19 21...

user output
(empty)

Test 25

Group: 2, 3, 4, 5, 6

Verdict:

input
50 11
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
687136
15 21 26 30 33 36 39 42 44 46 ...

user output
(empty)

Test 26

Group: 2, 3, 4, 5, 6

Verdict:

input
50 7
9996 4 9999 1 10000 0 10000 3 ...

correct output
27295930079
6 11 18 23 30 37 44

user output
27295930079

Test 27

Group: 2, 3, 4, 5, 6

Verdict:

input
50 14
9998 4 9997 1 9996 3 9999 1 99...

correct output
29000419931
2 5 8 11 16 19 24 28 31 34 37 ...

user output
(empty)

Test 28

Group: 3, 4, 5, 6

Verdict:

input
200 3
3 2 0 2 3 2 0 3 3 4 3 0 3 1 4 ...

correct output
610590000
197 198 199

user output
610590000

Test 29

Group: 3, 4, 5, 6

Verdict:

input
200 3
10000 10000 10000 3 1 2 1 0 3 ...

correct output
311760000
1 2 3

user output
311760000

Test 30

Group: 3, 4, 5, 6

Verdict:

input
200 199
9997 10000 10000 9998 9997 999...

correct output
1989216017013
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
(empty)

Test 31

Group: 3, 4, 5, 6

Verdict:

input
200 3
9996 9996 9998 9997 9998 9997 ...

correct output
1499437552673
50 100 150

user output
1499437552673

Test 32

Group: 3, 4, 5, 6

Verdict:

input
200 140
10000 10000 2 2 0 4 0 4 3 1 1 ...

correct output
1019625819
1 2 3 5 7 8 9 14 15 16 17 18 1...

user output
(empty)

Test 33

Group: 3, 4, 5, 6

Verdict:

input
200 180
10000 0 0 3 4 1 0 0 0 1 2 2 3 ...

correct output
107630884
3 4 5 9 10 11 12 13 14 15 16 1...

user output
(empty)

Test 34

Group: 3, 4, 5, 6

Verdict:

input
200 199
3930 8785 9349 8634 3375 397 4...

correct output
475357671774
1 2 3 4 5 6 7 8 9 10 11 12 13 ...

user output
(empty)

Test 35

Group: 3, 4, 5, 6

Verdict:

input
200 44
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
193556962
31 43 53 61 68 74 80 85 90 95 ...

user output
(empty)

Test 36

Group: 3, 4, 5, 6

Verdict:

input
200 28
9998 4 9996 0 9997 1 9998 1 99...

correct output
482389919803
8 16 21 28 34 41 48 55 62 70 7...

user output
(empty)

Test 37

Group: 3, 4, 5, 6

Verdict:

input
200 56
9999 3 9998 4 9997 1 9999 1 10...

correct output
490686959791
3 7 11 14 17 20 24 27 30 34 38...

user output
(empty)

Test 38

Group: 4, 5, 6

Verdict:

input
1000 3
4 4 0 4 3 4 3 1 3 3 4 0 1 0 4 ...

correct output
21503404
342 669 999

user output
21503404

Test 39

Group: 4, 5, 6

Verdict:

input
1000 3
10000 10000 1 3 3 0 2 3 3 0 0 ...

correct output
140412195
1 2 504

user output
140412195

Test 40

Group: 4, 5, 6

Verdict:

input
1000 199
10000 9998 9999 10000 10000 99...

correct output
49729674225461
5 10 15 20 25 30 35 40 45 50 5...

user output
(empty)

Test 41

Group: 4, 5, 6

Verdict:

input
1000 3
9998 9998 9996 9997 9998 9999 ...

correct output
37485571387523
250 500 750

user output
37485571387523

Test 42

Group: 4, 5, 6

Verdict:

input
1000 200
10000 10000 10000 3 0 4 4 2 2 ...

correct output
679388326
1 2 3 7 12 18 21 27 32 36 41 4...

user output
(empty)

Test 43

Group: 4, 5, 6

Verdict:

input
1000 170
10000 2 1 1 2 0 0 1 1 2 1 3 2 ...

correct output
4699030287
1 11 16 21 28 33 40 47 56 60 6...

user output
(empty)

Test 44

Group: 4, 5, 6

Verdict:

input
1000 200
7991 3892 7274 6053 1276 9944 ...

correct output
12418819758185
4 9 14 17 23 29 33 38 43 49 54...

user output
(empty)

Test 45

Group: 4, 5, 6

Verdict:

input
1000 200
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
31093317350
50 70 86 99 111 122 132 141 14...

user output
(empty)

Test 46

Group: 4, 5, 6

Verdict:

input
1000 40
9998 2 9996 0 9999 0 9997 2 99...

correct output
12194625429236
25 49 73 98 122 145 170 193 21...

user output
(empty)

Test 47

Group: 4, 5, 6

Verdict:

input
1000 80
9998 3 9997 2 9996 4 9996 4 99...

correct output
12345131038664
12 24 35 47 60 72 85 98 110 12...

user output
(empty)

Test 48

Group: 5, 6

Verdict:

input
10000 3
4 3 2 1 1 2 1 3 0 0 1 0 3 1 1 ...

correct output
1818678304
7492 9996 9998

user output
(empty)

Test 49

Group: 5, 6

Verdict:

input
10000 3
10000 10000 10000 10000 4 1 0 ...

correct output
1326260195
2 3 2455

user output
(empty)

Test 50

Group: 5, 6

Verdict:

input
10000 200
9997 9998 9999 10000 9996 9996...

correct output
4973126687469639
50 99 149 199 249 299 349 398 ...

user output
(empty)

Test 51

Group: 5, 6

Verdict:

input
10000 3
10000 9998 9996 9997 9999 9997...

correct output
3748491676694116
2500 5000 7500

user output
(empty)

Test 52

Group: 5, 6

Verdict:

input
10000 120
10000 10000 1 0 4 0 0 0 4 0 1 ...

correct output
1085432199
1 2 89 168 259 350 432 530 620...

user output
(empty)

Test 53

Group: 5, 6

Verdict:

input
10000 140
10000 4 2 0 1 1 4 2 0 3 2 2 0 ...

correct output
514790755404
54 101 200 277 345 420 501 600...

user output
(empty)

Test 54

Group: 5, 6

Verdict:

input
10000 150
8145 2828 5436 7600 6583 9304 ...

correct output
1256105310476641
71 147 212 276 340 395 461 539...

user output
(empty)

Test 55

Group: 5, 6

Verdict:

input
10000 122
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
3099592898816
202 286 350 404 452 495 537 58...

user output
(empty)

Test 56

Group: 5, 6

Verdict:

input
10000 140
9997 3 9997 0 9996 3 9997 1 99...

correct output
1241131419367412
70 141 212 282 354 424 493 564...

user output
(empty)

Test 57

Group: 5, 6

Verdict:

input
10000 180
9997 2 9998 2 10000 2 9996 3 9...

correct output
1243084101967798
56 110 165 221 276 331 385 440...

user output
(empty)

Test 58

Group: 6

Verdict:

input
100000 3
4 4 4 4 4 2 0 0 0 3 1 4 4 1 3 ...

correct output
19795776960
28624 57530 86260

user output
(empty)

Test 59

Group: 6

Verdict:

input
100000 3
10000 10000 10000 2 3 3 1 0 2 ...

correct output
19874432173
13758 42470 71322

user output
(empty)

Test 60

Group: 6

Verdict:

input
100000 200
9998 10000 9999 9996 9998 9996...

correct output
497313449256899208
498 996 1493 1990 2488 2986 34...

user output
(empty)

Test 61

Group: 6

Verdict:

input
100000 3
9999 9999 9996 9998 9996 9996 ...

correct output
374850090734572421
25000 50000 75000

user output
(empty)

Test 62

Group: 6

Verdict:

input
100000 200
10000 10000 10000 10000 10000 ...

correct output
36183271951
1 2 3 4 5 522 1035 1525 2031 2...

user output
(empty)

Test 63

Group: 6

Verdict:

input
100000 140
10000 3 1 0 0 1 4 2 3 2 3 0 1 ...

correct output
51629847150471
700 1398 2086 2800 3500 4201 4...

user output
(empty)

Test 64

Group: 6

Verdict:

input
100000 150
5874 361 291 3720 8802 8250 81...

correct output
124074747024496432
691 1355 2047 2739 3421 4065 4...

user output
(empty)

Test 65

Group: 6

Verdict:

input
100000 122
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
309959349080800
695 1568 2469 3355 4180 4753 5...

user output
(empty)

Test 66

Group: 6

Verdict:

input
100000 140
9996 0 9996 0 9997 0 10000 4 9...

correct output
124113525649823701
709 1419 2128 2836 3545 4254 4...

user output
(empty)

Test 67

Group: 6

Verdict:

input
100000 180
9998 4 9997 2 9996 4 9996 1 10...

correct output
124309619349406845
552 1103 1656 2209 2761 3314 3...

user output
(empty)