CSES - APIO 2014 - Results
Submission details
Task:Split the sequence
Sender:ollpu
Submission time:2019-03-23 19:07:43 +0200
Language:C++
Status:READY
Result:50
Feedback
groupverdictscore
#1ACCEPTED11
#2ACCEPTED11
#3ACCEPTED11
#4ACCEPTED17
#50
#60
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#2ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#3ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#4ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#5ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#6ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#7ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#8ACCEPTED0.03 s1, 2, 3, 4, 5, 6details
#9ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#10ACCEPTED0.01 s1, 2, 3, 4, 5, 6details
#11ACCEPTED0.03 s1, 2, 3, 4, 5, 6details
#12ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#13ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#14ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#15ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#16ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#17ACCEPTED0.02 s1, 2, 3, 4, 5, 6details
#18ACCEPTED0.01 s2, 3, 4, 5, 6details
#19ACCEPTED0.02 s2, 3, 4, 5, 6details
#20ACCEPTED0.01 s2, 3, 4, 5, 6details
#21ACCEPTED0.01 s2, 3, 4, 5, 6details
#22ACCEPTED0.02 s2, 3, 4, 5, 6details
#23ACCEPTED0.02 s2, 3, 4, 5, 6details
#24ACCEPTED0.02 s2, 3, 4, 5, 6details
#25ACCEPTED0.02 s2, 3, 4, 5, 6details
#26ACCEPTED0.01 s2, 3, 4, 5, 6details
#27ACCEPTED0.02 s2, 3, 4, 5, 6details
#28ACCEPTED0.01 s3, 4, 5, 6details
#29ACCEPTED0.01 s3, 4, 5, 6details
#30ACCEPTED0.04 s3, 4, 5, 6details
#31ACCEPTED0.02 s3, 4, 5, 6details
#32ACCEPTED0.03 s3, 4, 5, 6details
#33ACCEPTED0.02 s3, 4, 5, 6details
#34ACCEPTED0.03 s3, 4, 5, 6details
#35ACCEPTED0.02 s3, 4, 5, 6details
#36ACCEPTED0.01 s3, 4, 5, 6details
#37ACCEPTED0.02 s3, 4, 5, 6details
#38ACCEPTED0.02 s4, 5, 6details
#39ACCEPTED0.02 s4, 5, 6details
#40ACCEPTED0.22 s4, 5, 6details
#41ACCEPTED0.02 s4, 5, 6details
#42ACCEPTED0.22 s4, 5, 6details
#43ACCEPTED0.22 s4, 5, 6details
#44ACCEPTED0.23 s4, 5, 6details
#45ACCEPTED0.22 s4, 5, 6details
#46ACCEPTED0.07 s4, 5, 6details
#47ACCEPTED0.12 s4, 5, 6details
#48ACCEPTED0.45 s5, 6details
#49ACCEPTED0.38 s5, 6details
#50--5, 6details
#51ACCEPTED0.40 s5, 6details
#52--5, 6details
#53--5, 6details
#54--5, 6details
#55--5, 6details
#56--5, 6details
#57--5, 6details
#580.10 s6details
#590.09 s6details
#600.10 s6details
#610.09 s6details
#620.09 s6details
#630.09 s6details
#640.09 s6details
#650.10 s6details
#660.09 s6details
#670.09 s6details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:52:8: warning: 'xi' may be used uninitialized in this function [-Wmaybe-uninitialized]
     xi = dpr[xi][--k];
     ~~~^~~~~~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
const long INF = 4e18;
long dp[101010][200];
long dpr[101010][200];
int sa[101010];
long sag(int a, int b) {
  return sa[b+1]-sa[a];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int t[n];
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
  }
  for (int i = 0; i < n; ++i) {
    sa[i+1] = t[i];
    sa[i+1] += sa[i];
  }
  for (int i = 0; i < n-1; ++i) {
    dp[i][0] = sag(0, i)*sag(i+1, n-1);
    dpr[i][0] = -1;
  }
  for (int x = 1; x < k; ++x) {
    for (int i = 0; i < n-1; ++i) {
      dp[i][x] = -INF;
      for (int j = 0; j < i; ++j) {
        if (dp[j][x-1] == -INF) continue;
        long nv = dp[j][x-1]+sag(j+1, i)*sag(i+1, n-1);
        if (nv > dp[i][x]) {
          dp[i][x] = nv;
          dpr[i][x] = j;
        }
      }
    }
  }
  long res = -INF, xi;
  for (int i = 0; i < n-1; ++i) {
    if (dp[i][k-1] > res) {
      res = dp[i][k-1];
      xi = i;
    }
  }
  cout << res << endl;
  do {
    cout << xi+1 << " ";
    xi = dpr[xi][--k];
  } while (k);
  cout << endl;
}

Test details

Test 1

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

Verdict: ACCEPTED

input
7 3
4 1 3 4 0 2 3

correct output
108
1 3 5

user output
108
4 3 1 

Test 2

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

Verdict: ACCEPTED

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

correct output
999
6 8

user output
999
8 5 

Test 3

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

Verdict: ACCEPTED

input
2 1
0 123

correct output
0
1

user output
0

Test 4

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

Verdict: ACCEPTED

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

correct output
1542524
2 4 5 7 9

user output
1542524
9 7 5 4 2 

Test 5

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

Verdict: ACCEPTED

input
10 9
10000 10000 10000 10000 10000 ...

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

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

Test 6

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

Verdict: ACCEPTED

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: ACCEPTED

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: ACCEPTED

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: ACCEPTED

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

correct output
100400096
5 8 9

user output
100400096
9 8 4 

Test 10

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

Verdict: ACCEPTED

input
10 3
10000 10000 10000 10000 10000 ...

correct output
900320000
2 3 4

user output
900320000
4 2 1 

Test 11

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

Verdict: ACCEPTED

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

correct output
3698080248
2 5 8

user output
3698080248
7 4 2 

Test 12

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

Verdict: ACCEPTED

input
10 4
10000 10000 10000 10000 10000 ...

correct output
3200320000
2 4 6 8

user output
3200320000
8 6 4 2 

Test 13

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

Verdict: ACCEPTED

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

correct output
140072
1 4 6 7

user output
140072
7 6 3 1 

Test 14

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

Verdict: ACCEPTED

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

correct output
376041456
3 5 6

user output
376041456
6 5 3 

Test 15

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

Verdict: ACCEPTED

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

correct output
805
5 7 8 9

user output
805
9 8 7 5 

Test 16

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

Verdict: ACCEPTED

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

correct output
900189994
2 5 7

user output
900189994
7 5 2 

Test 17

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

Verdict: ACCEPTED

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

correct output
999919994
2 4 6 8

user output
999919994
8 5 4 1 

Test 18

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
49 32 14 

Test 19

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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

correct output
302460000
1 2 3

user output
302460000
3 2 1 

Test 20

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
122453454361
49 48 47 46 45 44 43 42 41 40 ...
Truncated

Test 21

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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

correct output
93663683509
12 25 37

user output
93663683509
37 25 12 

Test 22

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
1005304678
49 47 41 30 24 16 10 3 2 1 

Test 23

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
41 32 26 20 14 9 1 

Test 24

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
25082842857
47 43 41 39 38 37 35 32 29 27 ...

Test 25

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
687136
48 46 44 42 39 36 33 30 26 21 ...

Test 26

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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

correct output
27295930079
6 11 18 23 30 37 44

user output
27295930079
43 37 30 23 18 11 5 

Test 27

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

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
29000419931
46 43 41 37 34 31 28 24 19 16 ...

Test 28

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
199 198 197 

Test 29

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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

correct output
311760000
1 2 3

user output
311760000
3 2 1 

Test 30

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
1989216017013
199 198 197 196 195 194 193 19...
Truncated

Test 31

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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

correct output
1499437552673
50 100 150

user output
1499437552673
150 100 50 

Test 32

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
1019625819
199 198 197 196 195 194 193 19...
Truncated

Test 33

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
107630884
199 198 196 195 194 193 192 19...
Truncated

Test 34

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
475357671774
199 198 197 196 195 194 193 19...
Truncated

Test 35

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
193556962
198 196 194 192 190 188 186 18...
Truncated

Test 36

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
482389919803
191 185 179 172 165 159 151 14...
Truncated

Test 37

Group: 3, 4, 5, 6

Verdict: ACCEPTED

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
490686959791
196 192 189 185 182 178 174 17...
Truncated

Test 38

Group: 4, 5, 6

Verdict: ACCEPTED

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
998 667 341 

Test 39

Group: 4, 5, 6

Verdict: ACCEPTED

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

correct output
140412195
1 2 504

user output
140412195
504 2 1 

Test 40

Group: 4, 5, 6

Verdict: ACCEPTED

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
49729674225461
995 990 985 980 975 970 965 96...
Truncated

Test 41

Group: 4, 5, 6

Verdict: ACCEPTED

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

correct output
37485571387523
250 500 750

user output
37485571387523
750 500 250 

Test 42

Group: 4, 5, 6

Verdict: ACCEPTED

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
679388326
999 995 992 988 985 982 979 97...
Truncated

Test 43

Group: 4, 5, 6

Verdict: ACCEPTED

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
4699030287
996 993 986 976 971 968 960 95...
Truncated

Test 44

Group: 4, 5, 6

Verdict: ACCEPTED

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
12418819758185
995 992 988 983 979 976 972 96...
Truncated

Test 45

Group: 4, 5, 6

Verdict: ACCEPTED

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
31093317350
951 931 915 902 890 879 869 86...
Truncated

Test 46

Group: 4, 5, 6

Verdict: ACCEPTED

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
12194625429236
974 949 924 899 874 849 825 80...
Truncated

Test 47

Group: 4, 5, 6

Verdict: ACCEPTED

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
12345131038664
987 975 963 951 939 928 916 90...
Truncated

Test 48

Group: 5, 6

Verdict: ACCEPTED

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
1818678304
9998 9996 7492 

Test 49

Group: 5, 6

Verdict: ACCEPTED

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

correct output
1326260195
2 3 2455

user output
1326260195
2455 3 1 

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: ACCEPTED

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

correct output
3748491676694116
2500 5000 7500

user output
3748491676694116
7500 5000 2500 

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)