CSES - APIO 2015 - Results
Submission details
Task:Bali Sculptures
Sender:Yytsi
Submission time:2019-04-07 17:40:38 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.02 s1, 2, 3, 4, 5details
#2ACCEPTED0.02 s1, 2, 3, 4, 5details
#30.02 s1, 2, 3, 4, 5details
#40.02 s1, 2, 3, 4, 5details
#50.01 s1, 2, 3, 4, 5details
#60.02 s1, 2, 3, 4, 5details
#70.01 s1, 2, 3, 4, 5details
#80.03 s1, 2, 3, 4, 5details
#90.02 s1, 2, 3, 4, 5details
#100.01 s1, 2, 3, 4, 5details
#110.02 s1, 2, 3, 4, 5details
#120.02 s1, 2, 3, 4, 5details
#130.03 s1, 2, 4details
#140.01 s1, 2, 4details
#150.02 s1, 2, 4details
#160.03 s1, 2, 4details
#170.01 s1, 2, 4details
#180.01 s1, 2, 4details
#190.02 s1, 2, 4details
#200.03 s1, 2, 4details
#210.02 s1, 2, 4details
#220.01 s1, 2, 4details
#230.03 s1, 2, 4details
#240.02 s1, 2, 4details
#250.03 s1, 2, 4details
#260.02 s1, 4, 5details
#270.02 s1, 4, 5details
#280.01 s1, 4, 5details
#290.02 s1, 4, 5details
#300.01 s1, 4, 5details
#310.03 s1, 4, 5details
#320.02 s1, 4, 5details
#330.01 s1, 4, 5details
#340.02 s1, 4, 5details
#350.03 s1, 4, 5details
#360.01 s2, 3, 4, 5details
#370.01 s2, 3, 4, 5details
#380.02 s2, 3, 4, 5details
#390.02 s2, 3, 4, 5details
#400.01 s2, 3, 4, 5details
#410.01 s2, 3, 4, 5details
#420.01 s2, 3, 4, 5details
#430.03 s2, 3, 4, 5details
#440.02 s2, 3, 4, 5details
#450.02 s2, 3, 4, 5details
#460.01 s3, 4, 5details
#470.02 s3, 4, 5details
#480.01 s3, 4, 5details
#490.01 s3, 4, 5details
#500.02 s3, 4, 5details
#510.02 s3, 4, 5details
#520.02 s3, 4, 5details
#530.01 s3, 4, 5details
#540.03 s3, 4, 5details
#550.01 s4, 5details
#560.01 s4, 5details
#570.03 s4, 5details
#580.02 s4, 5details
#590.01 s4, 5details
#600.02 s4, 5details
#610.02 s4, 5details
#620.02 s4, 5details
#630.03 s4details
#640.01 s4details
#650.02 s4details
#660.02 s4details
#670.01 s4details
#680.02 s4details
#690.01 s4details
#700.01 s4details
#710.03 s4details
#720.02 s4details
#730.03 s4details
#740.03 s5details
#750.04 s5details
#760.04 s5details
#770.06 s5details
#780.06 s5details
#790.17 s5details
#800.17 s5details
#810.17 s5details
#820.16 s5details
#830.16 s5details
#840.01 s5details
#850.05 s5details
#860.05 s5details
#870.05 s5details
#880.08 s5details
#890.13 s5details
#900.17 s5details
#910.17 s5details
#920.16 s5details

Code

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define IO ios_base::sync_with_stdio(0); cin.tie(0)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;

int n, a, b;
ll val[2020];
ll dp[2020];

bool ok(ll ans) {
	FOR(i,1,n+1) {
		ll sm = 0;
		dp[i] = 1LL << 50;
		for (int j = i; j >= 1; j--) {
			sm += val[j];
			if ((ans & sm) == sm) dp[i] = min(dp[i], dp[j-1]+1);
		}
	}
	return dp[n] <= b;
}

int main() {
  IO; cin>>n>>a>>b;
  FOR(i,1,n+1) cin>>val[i];

  ll l = 0, r = 1LL << 50;
  while (l <= r) {
  	ll t = (l+r)/2LL;
  	if (ok(t)) r = t-1;
  	else l = t+1;
  }

  cout<<l<<"\n";
}

Test details

Test 1

Group: 1, 2, 3, 4, 5

Verdict:

input
8 1 4
1 2 1 1 1 0 4 6

correct output
6

user output
1125899906842603

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

input
1 1 1
0

correct output
0

user output
0

Test 3

Group: 1, 2, 3, 4, 5

Verdict:

input
5 1 3
3 4 8 8 6

correct output
15

user output
1125899906842623

Test 4

Group: 1, 2, 3, 4, 5

Verdict:

input
10 1 1
9 7 3 3 7 9 0 9 1 4

correct output
52

user output
1125899906842620

Test 5

Group: 1, 2, 3, 4, 5

Verdict:

input
15 1 15
0 7 4 1 3 1 0 5 4 3 9 1 3 1 3

correct output
11

user output
1125899906842623

Test 6

Group: 1, 2, 3, 4, 5

Verdict:

input
17 1 3
10 5 7 3 5 9 0 10 10 7 6 3 3 0...

correct output
47

user output
1125899906842618

Test 7

Group: 1, 2, 3, 4, 5

Verdict:

input
20 1 3
3 0 9 7 1 2 6 0 0 2 1 8 5 5 3 ...

correct output
43

user output
1125899906842623

Test 8

Group: 1, 2, 3, 4, 5

Verdict:

input
20 1 3
9 9 8 8 10 8 8 8 8 9 9 8 8 8 9...

correct output
62

user output
1125899906842621

Test 9

Group: 1, 2, 3, 4, 5

Verdict:

input
20 1 3
10 10 10 10 10 10 10 10 10 10 ...

correct output
94

user output
1125899906842612

Test 10

Group: 1, 2, 3, 4, 5

Verdict:

input
20 1 1
10 10 10 10 10 10 10 10 10 10 ...

correct output
200

user output
1125899906842616

Test 11

Group: 1, 2, 3, 4, 5

Verdict:

input
20 1 3
8 1 1 1 8 2 2 4 2 8 8 1 4 1 1 ...

correct output
27

user output
1125899906842611

Test 12

Group: 1, 2, 3, 4, 5

Verdict:

input
20 1 17
4 2 4 1 8 8 4 1 4 2 2 1 1 2 1 ...

correct output
11

user output
1125899906842623

Test 13

Group: 1, 2, 4

Verdict:

input
6 2 3
1 1 1 1 1 1

correct output
2

user output
1125899906842621

Test 14

Group: 1, 2, 4

Verdict:

input
6 6 6
0 0 0 1 1 2

correct output
3

user output
1125899906842618

Test 15

Group: 1, 2, 4

Verdict:

input
6 3 6
6 5 0 0 0 1

correct output
7

user output
1125899906842619

Test 16

Group: 1, 2, 4

Verdict:

input
5 2 3
7 5 6 9 8

correct output
15

user output
1125899906842623

Test 17

Group: 1, 2, 4

Verdict:

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

correct output
15

user output
1125899906842623

Test 18

Group: 1, 2, 4

Verdict:

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

correct output
15

user output
1125899906842621

Test 19

Group: 1, 2, 4

Verdict:

input
17 3 3
3 6 7 9 9 5 7 5 6 2 6 2 10 8 7...

correct output
43

user output
1125899906842618

Test 20

Group: 1, 2, 4

Verdict:

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

correct output
19

user output
1125899906842623

Test 21

Group: 1, 2, 4

Verdict:

input
20 4 7
10 10 8 10 9 10 10 8 10 9 9 8 ...

correct output
31

user output
1125899906842623

Test 22

Group: 1, 2, 4

Verdict:

input
20 4 7
10 10 10 10 10 10 10 10 10 10 ...

correct output
30

user output
1125899906842610

Test 23

Group: 1, 2, 4

Verdict:

input
20 2 2
10 10 10 10 10 10 10 10 10 10 ...

correct output
100

user output
1125899906842612

Test 24

Group: 1, 2, 4

Verdict:

input
20 2 7
1 4 8 1 4 4 1 1 2 8 2 2 4 1 1 ...

correct output
13

user output
1125899906842623

Test 25

Group: 1, 2, 4

Verdict:

input
20 5 13
1 4 8 1 2 8 1 1 8 8 8 4 4 2 2 ...

correct output
15

user output
1125899906842621

Test 26

Group: 1, 4, 5

Verdict:

input
5 1 3
484935714 268992075 426899299 ...

correct output
1023340543

user output
1125899906842623

Test 27

Group: 1, 4, 5

Verdict:

input
10 1 4
628673248 923554466 802711954 ...

correct output
1744830461

user output
1125899906842623

Test 28

Group: 1, 4, 5

Verdict:

input
13 1 13
606300077 908667444 394321231 ...

correct output
1073741823

user output
1125899906842623

Test 29

Group: 1, 4, 5

Verdict:

input
19 1 3
784661819 844802233 537453129 ...

correct output
4290772959

user output
1125899906842621

Test 30

Group: 1, 4, 5

Verdict:

input
20 1 7
1000000000 1000000000 10000000...

correct output
4000000000

user output
1125899906839040

Test 31

Group: 1, 4, 5

Verdict:

input
20 1 1
1000000000 1000000000 10000000...

correct output
20000000000

user output
1125899906840576

Test 32

Group: 1, 4, 5

Verdict:

input
20 1 13
16384 256 4194304 524288 4096 ...

correct output
384325888

user output
1125899906841856

Test 33

Group: 1, 4, 5

Verdict:

input
20 1 20
32 536870912 8192 131072 41943...

correct output
547320608

user output
1125899906842592

Test 34

Group: 1, 4, 5

Verdict:

input
20 1 3
16777216 262144 128 32 1024 16...

correct output
536207264

user output
1125899906842592

Test 35

Group: 1, 4, 5

Verdict:

input
20 1 20
256 33554432 128 8192 131072 8...

correct output
1073472416

user output
1125899906842592

Test 36

Group: 2, 3, 4, 5

Verdict:

input
21 1 20
2 8 9 5 5 2 8 3 0 5 0 5 9 3 4 ...

correct output
15

user output
1125899906842623

Test 37

Group: 2, 3, 4, 5

Verdict:

input
25 1 10
0 8 2 7 2 6 9 10 3 4 1 4 8 4 4...

correct output
23

user output
1125899906842623

Test 38

Group: 2, 3, 4, 5

Verdict:

input
38 1 5
8 8 4 5 5 3 7 10 6 1 3 10 3 2 ...

correct output
46

user output
1125899906842621

Test 39

Group: 2, 3, 4, 5

Verdict:

input
42 1 18
4 4 7 2 9 5 6 0 1 9 5 3 2 8 0 ...

correct output
15

user output
1125899906842611

Test 40

Group: 2, 3, 4, 5

Verdict:

input
50 1 20
8 8 9 10 10 8 9 8 8 9 10 9 8 1...

correct output
31

user output
1125899906842623

Test 41

Group: 2, 3, 4, 5

Verdict:

input
50 1 20
10 10 10 10 10 10 10 10 10 10 ...

correct output
30

user output
1125899906842618

Test 42

Group: 2, 3, 4, 5

Verdict:

input
50 1 1
10 10 10 10 10 10 10 10 10 10 ...

correct output
500

user output
1125899906842620

Test 43

Group: 2, 3, 4, 5

Verdict:

input
50 1 20
2 2 6 1 8 4 10 1 2 4 1 3 4 5 5...

correct output
15

user output
1125899906842617

Test 44

Group: 2, 3, 4, 5

Verdict:

input
50 1 17
4 10 3 4 2 8 6 6 4 2 8 8 5 4 9...

correct output
23

user output
1125899906842623

Test 45

Group: 2, 3, 4, 5

Verdict:

input
50 1 10
8 8 6 4 10 8 2 2 5 4 6 3 3 7 2...

correct output
31

user output
1125899906842623

Test 46

Group: 3, 4, 5

Verdict:

input
51 1 20
6 10 12 9 0 3 14 3 0 1 18 20 4...

correct output
31

user output
1125899906842623

Test 47

Group: 3, 4, 5

Verdict:

input
65 1 10
4 4 16 20 4 4 1 16 19 7 7 6 7 ...

correct output
79

user output
1125899906842623

Test 48

Group: 3, 4, 5

Verdict:

input
78 1 23
1 7 6 6 16 19 4 1 3 19 4 11 14...

correct output
47

user output
1125899906842621

Test 49

Group: 3, 4, 5

Verdict:

input
91 1 55
17 10 12 19 18 1 10 7 15 15 10...

correct output
31

user output
1125899906842621

Test 50

Group: 3, 4, 5

Verdict:

input
100 1 100
14 12 3 1 15 7 6 13 16 16 0 2 ...

correct output
31

user output
1125899906842623

Test 51

Group: 3, 4, 5

Verdict:

input
100 1 100
20 20 20 20 20 20 20 20 20 20 ...

correct output
20

user output
1125899906842596

Test 52

Group: 3, 4, 5

Verdict:

input
100 1 1
20 20 20 20 20 20 20 20 20 20 ...

correct output
2000

user output
1125899906842608

Test 53

Group: 3, 4, 5

Verdict:

input
100 1 47
18 1 15 15 2 14 19 16 8 19 1 7...

correct output
47

user output
1125899906842617

Test 54

Group: 3, 4, 5

Verdict:

input
100 1 74
18 7 6 16 5 12 15 13 20 18 20 ...

correct output
31

user output
1125899906842621

Test 55

Group: 4, 5

Verdict:

input
51 1 20
121196387 793437174 733664347 ...

correct output
2143289343

user output
1125899906842621

Test 56

Group: 4, 5

Verdict:

input
78 1 23
338917195 45092218 991962249 5...

correct output
2147483647

user output
1125899906842525

Test 57

Group: 4, 5

Verdict:

input
91 1 55
864333343 206114644 126507950 ...

correct output
1073741823

user output
1125899906842623

Test 58

Group: 4, 5

Verdict:

input
100 1 100
963428291 63818745 221600859 3...

correct output
1073741823

user output
1125899906842621

Test 59

Group: 4, 5

Verdict:

input
100 1 100
1000000000 1000000000 10000000...

correct output
1000000000

user output
1125899906839040

Test 60

Group: 4, 5

Verdict:

input
100 1 1
1000000000 1000000000 10000000...

correct output
100000000000

user output
1125899906840576

Test 61

Group: 4, 5

Verdict:

input
100 1 100
4729857 16400 9744 524296 4204...

correct output
1040187359

user output
1125899906842621

Test 62

Group: 4, 5

Verdict:

input
100 1 100
524800 268435472 3153920 52896...

correct output
1006630911

user output
1125899906842621

Test 63

Group: 4

Verdict:

input
90 45 90
0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 ...

correct output
2

user output
1125899906842618

Test 64

Group: 4

Verdict:

input
51 11 20
338656497 283890494 150485552 ...

correct output
2139095039

user output
1125899906842623

Test 65

Group: 4

Verdict:

input
65 2 10
425384156 386493235 539305167 ...

correct output
3154116607

user output
1125899906842623

Test 66

Group: 4

Verdict:

input
78 2 23
840979497 86262996 486127502 1...

correct output
3087007743

user output
1125899906842623

Test 67

Group: 4

Verdict:

input
91 19 55
809793899 214508559 841918281 ...

correct output
2147483135

user output
1125899906842623

Test 68

Group: 4

Verdict:

input
100 57 100
196269864 268098408 244902537 ...

correct output
1073741823

user output
1125899906842597

Test 69

Group: 4

Verdict:

input
100 57 100
1000000000 1000000000 10000000...

correct output
1000000000

user output
1125899906839040

Test 70

Group: 4

Verdict:

input
100 2 2
1000000000 1000000000 10000000...

correct output
50000000000

user output
1125899906839552

Test 71

Group: 4

Verdict:

input
100 2 100
570425344 74752 312541184 5190...

correct output
1006632927

user output
1125899906842623

Test 72

Group: 4

Verdict:

input
100 47 74
16777571 268439560 67108864 13...

correct output
1073676287

user output
1125899906842623

Test 73

Group: 4

Verdict:

input
100 33 66
554434568 42500608 541065216 3...

correct output
1065352959

user output
1125899906842623

Test 74

Group: 5

Verdict:

input
101 1 20
85935224 323057267 117347452 1...

correct output
3187671039

user output
1125899906842623

Test 75

Group: 5

Verdict:

input
575 1 99
77324562 741204988 396285802 5...

correct output
3221225471

user output
1125899906842623

Test 76

Group: 5

Verdict:

input
747 1 747
165703035 239516466 247451396 ...

correct output
1073741823

user output
1125899906842565

Test 77

Group: 5

Verdict:

input
999 1 20
770032430 298850322 436841858 ...

correct output
25633488895

user output
1125899906842623

Test 78

Group: 5

Verdict:

input
1000 1 55
421970300 595156571 662138730 ...

correct output
9663676415

user output
1125899906842593

Test 79

Group: 5

Verdict:

input
2000 1 1000
180685541 530949040 41342815 2...

correct output
2147483647

user output
1125899906842623

Test 80

Group: 5

Verdict:

input
2000 1 2000
372443635 870265368 711491467 ...

correct output
1073741823

user output
1125899906842617

Test 81

Group: 5

Verdict:

input
2000 1 2000
999999340 999999681 999999964 ...

correct output
1000001535

user output
1125899906842621

Test 82

Group: 5

Verdict:

input
2000 1 2000
1000000000 1000000000 10000000...

correct output
1000000000

user output
1125899906826752

Test 83

Group: 5

Verdict:

input
2000 1 1
1000000000 1000000000 10000000...

correct output
2000000000000

user output
1125899906834432

Test 84

Group: 5

Verdict:

input
101 1 20
555761664 2098187 134234368 54...

correct output
1073676287

user output
1125899906842621

Test 85

Group: 5

Verdict:

input
747 1 747
67371040 765321087 323789972 7...

correct output
1073741823

user output
1125899906842621

Test 86

Group: 5

Verdict:

input
999 1 20
819971511 671088634 273052483 ...

correct output
29796335615

user output
1125899906842593

Test 87

Group: 5

Verdict:

input
1000 1 1000
299890687 530448375 117474515 ...

correct output
1073741823

user output
1125899906842623

Test 88

Group: 5

Verdict:

input
1404 1 400
985503341 469745388 805302143 ...

correct output
3221225471

user output
1125899906842623

Test 89

Group: 5

Verdict:

input
1747 1 1747
503169023 620622781 994050047 ...

correct output
1073741823

user output
1125899906842623

Test 90

Group: 5

Verdict:

input
2000 1 1
939524095 989853695 939259903 ...

correct output
1376705763223

user output
1125899906842623

Test 91

Group: 5

Verdict:

input
2000 1 55
997711727 939524079 935329759 ...

correct output
25769803775

user output
1125899906842609

Test 92

Group: 5

Verdict:

input
2000 1 2000
805306367 939524087 536875520 ...

correct output
1073741823

user output
1125899906842621