QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#461862#138. Bali Sculpturesfryan37 36ms17280kbC++201.8kb2024-07-03 07:49:552024-07-03 07:49:55

Judging History

This is the latest submission verdict.

  • [2024-07-03 07:49:55]
  • Judged
  • Verdict: 37
  • Time: 36ms
  • Memory: 17280kb
  • [2024-07-03 07:49:55]
  • Submitted

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define i64 long long

const int mxn = 2e3+1;

int n,a,b;
i64 arr[mxn];

i64 rsq(int l, int r) {
	return (l ? arr[r] - arr[l-1] : arr[r]);
}

const int lg = 50;
i64 bd = (1ll<<(lg+1))-1;
int dp[mxn];

i64 suff(int n, int i) {
	return ((n>>i)<<i);
}

int is_submask(i64 a, i64 m) {
	return ((a&m) == a);
}

void process(int bt) {
	bd -= (1ll<<bt);

	memset(dp,0x3f,sizeof(dp));
	dp[0] = 0;
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<=n; j++) {
			int va = rsq(i+1,j);
			if (!is_submask(suff(va,bt),suff(bd,bt))) continue;
			dp[j] = min(dp[j], dp[i]+1);
		}
	}

	if (dp[n] > b) {
		bd += (1ll<<bt);
	}
}

int dp1[mxn][mxn];

void process1(int bt) {
	bd -= (1ll<<bt);
	memset(dp1, 0, sizeof(dp1));
	dp1[0][0] = 1;
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (!dp1[i][j]) continue;
			for (int k=i+1; k<=n; k++) {
				int va = rsq(i+1,k);
				if (!is_submask(suff(va,bt),suff(bd,bt))) continue;
				dp1[k][j+1] = 1;
			}
		}
	}
	for (int i=a; i<=b; i++) {
		if (dp1[n][i]) {
			return;
		}
	}
	bd += (1ll<<bt);
}

signed main() {
	
	scanf("%d%d%d",&n,&a,&b);
	for (int i=1; i<=n; i++) {
		scanf("%lld",&arr[i]);
		arr[i] += arr[i-1];
	}
	for (int m=lg; m>=0; m--) {
		if (a == 1) process(m);
		else process1(m);
	}
	printf("%lld",bd);
	
	
	return 0;
}

详细

Subtask #1:

score: 0
Accepted

Test #1:

score: 0
Accepted
time: 0ms
memory: 1592kb

input:

8 1 4
1 2 1 1 1 0 4 6

output:

6

result:

ok single line: '6'

Test #2:

score: 0
Accepted
time: 0ms
memory: 1652kb

input:

20 1 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

200

result:

ok single line: '200'

Test #3:

score: 0
Accepted
time: 0ms
memory: 1620kb

input:

20 1 3
8 1 1 1 8 2 2 4 2 8 8 1 4 1 1 4 2 4 2 8

output:

27

result:

ok single line: '27'

Test #4:

score: 0
Accepted
time: 0ms
memory: 1600kb

input:

20 1 17
4 2 4 1 8 8 4 1 4 2 2 1 1 2 1 8 1 8 1 2

output:

11

result:

ok single line: '11'

Test #5:

score: 0
Accepted
time: 0ms
memory: 1664kb

input:

1 1 1
0

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 1596kb

input:

5 1 3
3 4 8 8 6

output:

15

result:

ok single line: '15'

Test #7:

score: 0
Accepted
time: 0ms
memory: 1496kb

input:

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

output:

52

result:

ok single line: '52'

Test #8:

score: 0
Accepted
time: 0ms
memory: 1568kb

input:

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

output:

11

result:

ok single line: '11'

Test #9:

score: 0
Accepted
time: 0ms
memory: 1608kb

input:

17 1 3
10 5 7 3 5 9 0 10 10 7 6 3 3 0 6 8 8

output:

47

result:

ok single line: '47'

Test #10:

score: 0
Accepted
time: 0ms
memory: 1632kb

input:

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

output:

43

result:

ok single line: '43'

Test #11:

score: 0
Accepted
time: 0ms
memory: 1660kb

input:

20 1 3
9 9 8 8 10 8 8 8 8 9 9 8 8 8 9 8 10 8 9 8

output:

62

result:

ok single line: '62'

Test #12:

score: 0
Accepted
time: 0ms
memory: 1556kb

input:

20 1 3
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

94

result:

ok single line: '94'

Subtask #2:

score: 0
Accepted

Test #13:

score: 0
Accepted
time: 26ms
memory: 17236kb

input:

6 2 3
1 1 1 1 1 1

output:

2

result:

ok single line: '2'

Test #14:

score: 0
Accepted
time: 25ms
memory: 17240kb

input:

20 4 7
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

30

result:

ok single line: '30'

Test #15:

score: 0
Accepted
time: 26ms
memory: 17256kb

input:

20 2 2
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

100

result:

ok single line: '100'

Test #16:

score: 0
Accepted
time: 24ms
memory: 17248kb

input:

20 2 7
1 4 8 1 4 4 1 1 2 8 2 2 4 1 1 1 8 2 2 4

output:

13

result:

ok single line: '13'

Test #17:

score: 0
Accepted
time: 24ms
memory: 17280kb

input:

20 5 13
1 4 8 1 2 8 1 1 8 8 8 4 4 2 2 1 2 4 8 1

output:

15

result:

ok single line: '15'

Test #18:

score: 0
Accepted
time: 24ms
memory: 17264kb

input:

6 6 6
0 0 0 1 1 2

output:

3

result:

ok single line: '3'

Test #19:

score: 0
Accepted
time: 28ms
memory: 17252kb

input:

6 3 6
6 5 0 0 0 1

output:

7

result:

ok single line: '7'

Test #20:

score: 0
Accepted
time: 25ms
memory: 17280kb

input:

5 2 3
7 5 6 9 8

output:

15

result:

ok single line: '15'

Test #21:

score: 0
Accepted
time: 26ms
memory: 17280kb

input:

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

output:

15

result:

ok single line: '15'

Test #22:

score: 0
Accepted
time: 28ms
memory: 17188kb

input:

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

output:

15

result:

ok single line: '15'

Test #23:

score: 0
Accepted
time: 29ms
memory: 17192kb

input:

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

output:

43

result:

ok single line: '43'

Test #24:

score: 0
Accepted
time: 26ms
memory: 17280kb

input:

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

output:

19

result:

ok single line: '19'

Test #25:

score: 0
Accepted
time: 26ms
memory: 17184kb

input:

20 4 7
10 10 8 10 9 10 10 8 10 9 9 8 10 8 8 10 10 9 8 9

output:

31

result:

ok single line: '31'

Subtask #3:

score: 0
Wrong Answer

Test #26:

score: 0
Accepted
time: 0ms
memory: 1556kb

input:

5 1 3
451631570 250518388 397580948 477427142 699144811

output:

1040187263

result:

ok single line: '1040187263'

Test #27:

score: 0
Accepted
time: 0ms
memory: 1664kb

input:

20 1 20
262144 512 33554432 256 16384 32 8388608 2097152 536870912 524288 64 1024 32768 134217728 67108864 2048 4096 128 268435456 1048576

output:

1052565472

result:

ok single line: '1052565472'

Test #28:

score: -0
Wrong Answer
time: 0ms
memory: 1612kb

input:

10 1 4
585497577 747583750 169121856 897466290 878323190 352710279 143784633 220521827 564660939 846262488

output:

1073216509

result:

wrong answer 1st lines differ - expected: '1877999615', found: '1073216509'

Subtask #4:

score: 0
Accepted

Test #36:

score: 0
Accepted
time: 0ms
memory: 1648kb

input:

21 1 20
7 2 8 9 5 5 2 8 3 0 5 0 5 9 3 4 1 4 7 7 10

output:

15

result:

ok single line: '15'

Test #37:

score: 0
Accepted
time: 0ms
memory: 1648kb

input:

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

output:

31

result:

ok single line: '31'

Test #38:

score: 0
Accepted
time: 0ms
memory: 1624kb

input:

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

output:

23

result:

ok single line: '23'

Test #39:

score: 0
Accepted
time: 0ms
memory: 1612kb

input:

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

output:

47

result:

ok single line: '47'

Test #40:

score: 0
Accepted
time: 0ms
memory: 1480kb

input:

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

output:

15

result:

ok single line: '15'

Test #41:

score: 0
Accepted
time: 0ms
memory: 1564kb

input:

50 1 20
9 8 8 9 10 10 8 9 8 8 9 10 9 8 10 9 9 10 8 10 8 8 10 9 10 10 9 9 9 10 8 8 9 9 10 9 10 8 9 9 8 9 8 9 10 10 9 9 9 9

output:

27

result:

ok single line: '27'

Test #42:

score: 0
Accepted
time: 0ms
memory: 1624kb

input:

50 1 20
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

30

result:

ok single line: '30'

Test #43:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

50 1 1
10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10

output:

500

result:

ok single line: '500'

Test #44:

score: 0
Accepted
time: 0ms
memory: 1644kb

input:

50 1 20
2 2 6 1 8 4 10 1 2 4 1 3 4 5 5 4 2 5 1 4 8 3 9 8 4 6 5 10 6 6 6 2 4 5 8 3 8 1 1 4 4 10 4 4 6 3 7 3 6 8

output:

15

result:

ok single line: '15'

Test #45:

score: 0
Accepted
time: 0ms
memory: 1648kb

input:

50 1 17
4 10 3 4 2 8 6 6 4 2 8 8 5 4 9 4 10 1 4 6 3 8 3 3 8 3 8 9 8 5 5 2 8 3 8 1 9 9 6 1 10 10 8 7 1 9 8 2 5 9

output:

23

result:

ok single line: '23'

Subtask #5:

score: 0
Accepted

Test #46:

score: 0
Accepted
time: 0ms
memory: 1568kb

input:

51 1 20
6 10 12 9 0 3 14 3 0 1 18 20 4 9 7 16 11 15 17 16 10 15 11 1 6 16 19 15 12 17 10 3 6 5 14 6 11 0 18 6 0 2 4 7 7 16 7 9 10 13 0

output:

31

result:

ok single line: '31'

Test #47:

score: 0
Accepted
time: 0ms
memory: 1616kb

input:

65 1 10
4 4 16 20 4 4 1 16 19 7 7 6 7 13 3 17 6 1 18 4 18 11 10 5 6 16 19 12 15 11 1 2 11 9 17 2 3 18 18 4 14 19 6 8 0 16 7 5 17 10 1 12 2 7 17 15 12 13 18 2 12 7 12 8 14

output:

79

result:

ok single line: '79'

Test #48:

score: 0
Accepted
time: 0ms
memory: 1612kb

input:

78 1 23
1 7 6 6 16 19 4 1 3 19 4 11 14 5 11 6 18 15 3 19 1 16 3 11 9 18 4 3 16 5 15 20 19 16 20 15 7 11 4 13 8 5 11 16 5 19 10 0 11 13 16 3 9 13 13 4 9 4 8 18 4 15 15 1 1 2 15 19 9 9 12 14 1 12 10 16 9 1

output:

47

result:

ok single line: '47'

Test #49:

score: 0
Accepted
time: 0ms
memory: 1628kb

input:

91 1 55
17 10 12 19 18 1 10 7 15 15 10 8 1 4 20 1 6 4 11 11 2 3 17 5 20 4 11 6 6 20 1 0 2 5 19 15 9 20 18 1 2 17 14 5 11 14 13 12 11 13 4 16 20 8 13 6 0 7 15 10 15 2 19 17 0 16 17 16 18 2 3 13 12 7 20 6 1 17 6 4 5 19 11 18 5 19 12 17 15 8 11

output:

31

result:

ok single line: '31'

Test #50:

score: 0
Accepted
time: 0ms
memory: 1604kb

input:

100 1 100
14 12 3 1 15 7 6 13 16 16 0 2 12 5 13 6 18 18 3 5 13 14 5 19 12 20 2 1 2 4 13 14 4 13 9 12 4 20 1 10 10 19 10 5 1 7 3 15 9 4 2 9 10 20 15 10 11 13 5 12 2 15 8 1 18 5 7 15 4 11 9 18 20 14 10 8 9 10 18 10 11 0 7 12 6 15 19 0 9 0 15 19 0 2 20 0 9 1 20 17

output:

31

result:

ok single line: '31'

Test #51:

score: 0
Accepted
time: 0ms
memory: 1628kb

input:

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

output:

20

result:

ok single line: '20'

Test #52:

score: 0
Accepted
time: 0ms
memory: 1612kb

input:

100 1 1
20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 2...

output:

2000

result:

ok single line: '2000'

Test #53:

score: 0
Accepted
time: 0ms
memory: 1608kb

input:

100 1 47
18 1 15 15 2 14 19 16 8 19 1 7 12 5 16 1 5 15 13 15 16 20 8 20 9 13 7 19 8 2 4 4 4 17 5 19 19 16 2 5 13 19 9 19 5 14 17 7 12 13 16 8 7 20 10 20 7 14 19 2 9 8 11 18 19 12 9 13 20 16 10 15 9 16 17 6 20 2 19 20 15 20 8 11 12 4 20 18 1 13 8 1 9 16 12 18 17 1 3 19

output:

47

result:

ok single line: '47'

Test #54:

score: 0
Accepted
time: 0ms
memory: 1628kb

input:

100 1 74
18 7 6 16 5 12 15 13 20 18 20 7 14 19 7 19 19 15 11 16 12 16 1 20 20 12 11 18 17 14 2 9 13 6 2 8 14 11 2 7 14 19 11 20 20 13 18 16 4 10 15 9 17 20 13 15 15 7 7 8 12 20 10 15 15 11 14 19 4 16 1 19 5 17 2 4 7 20 11 1 9 7 4 10 20 19 20 11 20 16 16 11 9 17 3 17 14 12 19 18

output:

31

result:

ok single line: '31'

Subtask #6:

score: 0
Wrong Answer

Test #55:

score: 0
Wrong Answer
time: 0ms
memory: 1624kb

input:

51 1 20
112872931 738945953 683278169 770763749 516510818 790818428 875172481 703986370 60868760 918060338 785761560 775662511 633498896 598270657 590667589 115223551 657182582 662359373 423527461 442741161 404625684 341975402 396747626 126186088 753822361 159840892 743886212 135361223 217348329 815...

output:

738196479

result:

wrong answer 1st lines differ - expected: '1879048191', found: '738196479'

Subtask #7:

score: 0
Wrong Answer

Test #63:

score: 0
Accepted
time: 35ms
memory: 17256kb

input:

90 45 90
0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2 0 0 0 1 1 2

output:

2

result:

ok single line: '2'

Test #64:

score: -0
Wrong Answer
time: 36ms
memory: 17184kb

input:

100 47 74
268439560 67108864 135266304 42074240 8192 654311440 3146005 151136512 25346080 32996 539000832 814809088 589824 9048320 67240448 134218368 331844 2113577 524288 545260544 78208 256 50335808 16793604 536875016 50331688 285212684 274860032 1048576 8192 671105024 262144 41364 805339152 2048 ...

output:

1040186879

result:

wrong answer 1st lines differ - expected: '1073676287', found: '1040186879'

Subtask #8:

score: 0
Wrong Answer

Test #74:

score: 0
Wrong Answer
time: 0ms
memory: 1624kb

input:

101 1 20
109288331 167187936 289459547 455669706 656308194 233503022 562258473 2210429 243994669 58628149 750503963 610269250 29072940 251143410 458350486 696874700 870849343 646709707 646709077 746808795 87439926 187779526 762073671 569489420 380238922 982163795 784978520 933220915 264403502 755738...

output:

402587643

result:

wrong answer 1st lines differ - expected: '3221159935', found: '402587643'

Subtask #9:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%

Subtask #10:

score: 16
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #4:

100%
Accepted

Subtask #11:

score: 21
Accepted

Dependency #1:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Subtask #12:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%

Subtask #13:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #3:

0%