QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#106990#3170. Lunchtime Name Recallmarsxiang5902AC ✓253ms4648kbC++171.4kb2023-05-20 01:35:442023-05-20 01:35:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-20 01:35:45]
  • 评测
  • 测评结果：AC
  • 用时：253ms
  • 内存：4648kb
查看
  • [2023-05-20 01:35:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int MN = 30, BS = 1<<MN-1;

int N, M, ar[MN], cur[MN], n, s1; bitset<BS> vis; vector<int> dpPv, dpCur, v, ss;

void rec(int i) {
  if (i == n) {
    int rch = 1;
    for (int s: ss)
      rch |= rch << s;
    if (~rch & 1<<s1) return;
    int b = 0;
    for (int j = N; j; j--)
      for (int k = 0; k < cur[j]; k++)
        b <<= j, b |= 1<<j-1;
    b ^= 1<<N-1;
    if (!vis[b]) dpCur.push_back(b), vis.set(b);
    return;
  }
  for (int j = min(v[i]>>1, s1); j >= 0; j--) {
    ++cur[j]; ++cur[v[i]-j];
    s1 -= j; ss.push_back(v[i]-j - j);
    rec(i+1);
    s1 += j; ss.pop_back();
    --cur[j]; --cur[v[i]-j];
  }
}

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  cin >> N >> M;
  for (int i = 0; i < M; i++) {
    cin >> ar[i];
    ar[i] = min(ar[i], N-ar[i]);
  } sort(ar, ar+M);
  vis.set(0);
  dpPv.push_back(0);
  int ans = 0;
  for (int si = 0; si < M; si++) {
    s1 = ar[si];
    for (int b: dpPv) {
      b |= 1<<N-1;
      v.clear();
      while (b) {
        int c = __builtin_ctz(b);
        v.push_back(c+1);
        b >>= c+1;
      } n = v.size();
      assert(s1 == ar[si]);
      rec(0);
    }
    for (int b: dpCur)
      ans = max(ans, __builtin_ctz(~(b|1<<N-1)));
    swap(dpPv, dpCur);
    dpCur.clear();
  }
  printf("%d\n", ans);

  return 0;
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3708kb

input:

4 2
2
2

output:

4

result:

ok single line: '4'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

16 3
6
8
8

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3600kb

input:

5 2
2
2

output:

3

result:

ok single line: '3'

Test #4:

score: 0
Accepted
time: 2ms
memory: 3500kb

input:

16 3
8
8
8

output:

6

result:

ok single line: '6'

Test #5:

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

input:

20 7
1
1
1
1
6
8
8

output:

11

result:

ok single line: '11'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

7 3
3
2
1

output:

4

result:

ok single line: '4'

Test #7:

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

input:

9 4
1
1
3
3

output:

5

result:

ok single line: '5'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

10 3
4
4
3

output:

6

result:

ok single line: '6'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3732kb

input:

10 3
4
4
5

output:

6

result:

ok single line: '6'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3572kb

input:

10 3
4
4
4

output:

7

result:

ok single line: '7'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3760kb

input:

12 3
6
6
6

output:

6

result:

ok single line: '6'

Test #12:

score: 0
Accepted
time: 2ms
memory: 3540kb

input:

10 5
2
2
2
2
2

output:

7

result:

ok single line: '7'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3440kb

input:

10 6
2
2
2
2
2
2

output:

10

result:

ok single line: '10'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

10 2
3
3

output:

2

result:

ok single line: '2'

Test #15:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

10 6
8
5
2
8
8
1

output:

10

result:

ok single line: '10'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3556kb

input:

7 4
5
5
1
2

output:

5

result:

ok single line: '5'

Test #17:

score: 0
Accepted
time: 2ms
memory: 3436kb

input:

2 1
1

output:

2

result:

ok single line: '2'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3604kb

input:

3 1
1

output:

1

result:

ok single line: '1'

Test #19:

score: 0
Accepted
time: 1ms
memory: 3536kb

input:

30 1
15

output:

0

result:

ok single line: '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 3696kb

input:

3 5
1
1
1
1
1

output:

3

result:

ok single line: '3'

Test #21:

score: 0
Accepted
time: 2ms
memory: 3540kb

input:

5 6
2
2
2
2
2
2

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 185ms
memory: 4524kb

input:

30 5
15
15
15
15
13

output:

28

result:

ok single line: '28'

Test #23:

score: 0
Accepted
time: 38ms
memory: 4648kb

input:

30 10
15
15
15
15
15
1
1
1
1
1

output:

30

result:

ok single line: '30'

Test #24:

score: 0
Accepted
time: 39ms
memory: 4408kb

input:

30 10
15
10
10
10
10
1
1
1
1
1

output:

28

result:

ok single line: '28'

Test #25:

score: 0
Accepted
time: 203ms
memory: 4616kb

input:

30 7
9
9
9
9
9
9
2

output:

28

result:

ok single line: '28'

Test #26:

score: 0
Accepted
time: 113ms
memory: 4452kb

input:

30 10
2
2
2
3
3
3
6
11
14
15

output:

28

result:

ok single line: '28'

Test #27:

score: 0
Accepted
time: 140ms
memory: 4556kb

input:

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

output:

30

result:

ok single line: '30'

Test #28:

score: 0
Accepted
time: 253ms
memory: 4408kb

input:

30 10
11
12
13
14
15
16
17
18
19
20

output:

30

result:

ok single line: '30'

Test #29:

score: 0
Accepted
time: 143ms
memory: 4388kb

input:

30 10
20
21
22
23
24
25
26
27
28
29

output:

30

result:

ok single line: '30'

Test #30:

score: 0
Accepted
time: 54ms
memory: 4312kb

input:

30 10
4
4
4
5
5
5
5
5
5
5

output:

28

result:

ok single line: '28'

Test #31:

score: 0
Accepted
time: 118ms
memory: 4288kb

input:

30 10
2
2
2
3
3
3
8
8
9
11

output:

28

result:

ok single line: '28'

Test #32:

score: 0
Accepted
time: 113ms
memory: 4384kb

input:

30 10
2
2
2
3
3
3
9
9
9
9

output:

28

result:

ok single line: '28'

Test #33:

score: 0
Accepted
time: 123ms
memory: 4352kb

input:

30 10
12
12
12
12
3
2
2
2
2
2

output:

28

result:

ok single line: '28'

Test #34:

score: 0
Accepted
time: 118ms
memory: 4388kb

input:

30 10
10
9
9
9
3
3
2
2
2
2

output:

28

result:

ok single line: '28'

Test #35:

score: 0
Accepted
time: 122ms
memory: 4476kb

input:

30 10
10
9
9
8
5
2
2
2
2
2

output:

28

result:

ok single line: '28'

Test #36:

score: 0
Accepted
time: 104ms
memory: 4356kb

input:

30 10
9
9
9
8
8
3
2
2
1
1

output:

28

result:

ok single line: '28'

Test #37:

score: 0
Accepted
time: 2ms
memory: 3444kb

input:

30 10
1
1
1
1
1
1
1
1
1
1

output:

10

result:

ok single line: '10'

Test #38:

score: 0
Accepted
time: 2ms
memory: 3520kb

input:

30 10
2
2
2
2
2
2
2
2
2
2

output:

15

result:

ok single line: '15'

Test #39:

score: 0
Accepted
time: 5ms
memory: 3612kb

input:

30 10
3
3
3
3
3
3
3
3
3
3

output:

20

result:

ok single line: '20'

Test #40:

score: 0
Accepted
time: 14ms
memory: 4480kb

input:

30 10
4
4
4
4
4
4
4
4
4
4

output:

25

result:

ok single line: '25'

Test #41:

score: 0
Accepted
time: 52ms
memory: 4392kb

input:

30 10
5
5
5
5
5
5
5
5
5
5

output:

30

result:

ok single line: '30'

Test #42:

score: 0
Accepted
time: 1ms
memory: 3540kb

input:

30 3
2
2
2

output:

4

result:

ok single line: '4'

Test #43:

score: 0
Accepted
time: 2ms
memory: 3544kb

input:

30 6
2
2
2
2
2
2

output:

9

result:

ok single line: '9'

Test #44:

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

input:

30 9
2
2
2
2
2
2
2
2
2

output:

13

result:

ok single line: '13'

Test #45:

score: 0
Accepted
time: 71ms
memory: 4384kb

input:

30 10
2
3
4
5
5
5
5
5
6
6

output:

28

result:

ok single line: '28'

Test #46:

score: 0
Accepted
time: 60ms
memory: 4304kb

input:

30 10
2
4
5
5
5
5
5
5
5
6

output:

28

result:

ok single line: '28'

Test #47:

score: 0
Accepted
time: 15ms
memory: 4380kb

input:

30 10
15
15
15
15
29
29
29
29
29
29

output:

20

result:

ok single line: '20'

Test #48:

score: 0
Accepted
time: 160ms
memory: 4280kb

input:

30 5
15
15
15
15
15

output:

30

result:

ok single line: '30'

Test #49:

score: 0
Accepted
time: 72ms
memory: 4604kb

input:

30 10
3
6
6
7
4
3
5
3
6
4

output:

28

result:

ok single line: '28'

Test #50:

score: 0
Accepted
time: 106ms
memory: 4408kb

input:

30 10
5
2
6
7
4
7
3
4
2
6

output:

28

result:

ok single line: '28'

Test #51:

score: 0
Accepted
time: 243ms
memory: 4356kb

input:

30 10
20
6
20
19
11
18
21
24
18
12

output:

30

result:

ok single line: '30'

Test #52:

score: 0
Accepted
time: 220ms
memory: 4428kb

input:

30 10
7
22
8
12
12
23
10
11
24
21

output:

30

result:

ok single line: '30'

Test #53:

score: 0
Accepted
time: 225ms
memory: 4408kb

input:

30 10
19
21
23
17
8
21
15
20
6
22

output:

30

result:

ok single line: '30'

Test #54:

score: 0
Accepted
time: 243ms
memory: 4468kb

input:

30 10
16
5
19
16
10
14
10
12
14
4

output:

30

result:

ok single line: '30'

Test #55:

score: 0
Accepted
time: 215ms
memory: 4436kb

input:

30 10
5
9
7
10
6
21
15
24
17
21

output:

30

result:

ok single line: '30'

Test #56:

score: 0
Accepted
time: 85ms
memory: 4280kb

input:

30 10
2
4
7
3
2
6
7
2
5
2

output:

25

result:

ok single line: '25'

Test #57:

score: 0
Accepted
time: 120ms
memory: 4600kb

input:

30 10
8
6
4
2
2
3
4
8
6
5

output:

30

result:

ok single line: '30'

Test #58:

score: 0
Accepted
time: 88ms
memory: 4448kb

input:

30 10
6
4
6
4
5
2
3
3
5
8

output:

28

result:

ok single line: '28'

Test #59:

score: 0
Accepted
time: 34ms
memory: 4300kb

input:

30 10
4
12
8
13
8
1
1
1
1
1

output:

24

result:

ok single line: '24'

Test #60:

score: 0
Accepted
time: 36ms
memory: 4632kb

input:

30 10
7
13
6
9
14
1
1
1
1
1

output:

25

result:

ok single line: '25'

Test #61:

score: 0
Accepted
time: 31ms
memory: 4548kb

input:

30 10
5
11
8
14
9
1
1
1
1
1

output:

25

result:

ok single line: '25'

Test #62:

score: 0
Accepted
time: 40ms
memory: 4516kb

input:

30 10
4
12
5
12
1
3
1
2
1
3

output:

22

result:

ok single line: '22'

Test #63:

score: 0
Accepted
time: 31ms
memory: 4380kb

input:

30 10
6
13
12
10
1
2
1
2
1
1

output:

21

result:

ok single line: '21'

Test #64:

score: 0
Accepted
time: 70ms
memory: 4296kb

input:

30 10
7
5
14
5
1
3
2
3
2
2

output:

24

result:

ok single line: '24'

Test #65:

score: 0
Accepted
time: 224ms
memory: 4548kb

input:

30 5
12
14
15
12
15

output:

27

result:

ok single line: '27'

Test #66:

score: 0
Accepted
time: 224ms
memory: 4400kb

input:

30 5
14
13
15
11
11

output:

26

result:

ok single line: '26'

Test #67:

score: 0
Accepted
time: 236ms
memory: 4340kb

input:

30 5
13
12
14
11
12

output:

26

result:

ok single line: '26'

Test #68:

score: 0
Accepted
time: 239ms
memory: 4400kb

input:

30 6
11
10
9
9
10
9

output:

28

result:

ok single line: '28'

Test #69:

score: 0
Accepted
time: 236ms
memory: 4428kb

input:

30 6
10
7
8
11
9
9

output:

27

result:

ok single line: '27'

Test #70:

score: 0
Accepted
time: 232ms
memory: 4428kb

input:

30 6
7
9
8
10
10
8

output:

26

result:

ok single line: '26'

Test #71:

score: 0
Accepted
time: 221ms
memory: 4440kb

input:

30 7
6
10
7
9
6
8
9

output:

30

result:

ok single line: '30'

Test #72:

score: 0
Accepted
time: 200ms
memory: 4412kb

input:

30 7
7
6
7
10
7
7
10

output:

30

result:

ok single line: '30'

Test #73:

score: 0
Accepted
time: 185ms
memory: 4408kb

input:

30 7
7
8
6
8
8
7
6

output:

28

result:

ok single line: '28'

Test #74:

score: 0
Accepted
time: 102ms
memory: 4384kb

input:

30 10
2
2
4
5
8
5
4
11
3
3

output:

28

result:

ok single line: '28'

Test #75:

score: 0
Accepted
time: 128ms
memory: 4572kb

input:

30 9
5
2
3
3
8
10
6
3
6

output:

27

result:

ok single line: '27'

Test #76:

score: 0
Accepted
time: 72ms
memory: 4444kb

input:

30 9
5
2
3
3
8
8
4
3
3

output:

24

result:

ok single line: '24'

Test #77:

score: 0
Accepted
time: 108ms
memory: 4384kb

input:

30 10
3
2
6
4
1
8
4
8
4
6

output:

28

result:

ok single line: '28'

Test #78:

score: 0
Accepted
time: 133ms
memory: 4416kb

input:

30 9
3
6
6
11
2
7
4
2
6

output:

27

result:

ok single line: '27'

Test #79:

score: 0
Accepted
time: 115ms
memory: 4356kb

input:

30 10
3
8
6
5
2
7
4
2
2
7

output:

28

result:

ok single line: '28'

Test #80:

score: 0
Accepted
time: 146ms
memory: 4276kb

input:

30 9
3
6
4
2
7
8
5
8
4

output:

28

result:

ok single line: '28'

Test #81:

score: 0
Accepted
time: 135ms
memory: 4452kb

input:

30 9
8
7
6
4
7
2
5
6
2

output:

28

result:

ok single line: '28'

Test #82:

score: 0
Accepted
time: 108ms
memory: 4576kb

input:

30 10
3
5
2
7
7
1
6
2
6
7

output:

28

result:

ok single line: '28'

Test #83:

score: 0
Accepted
time: 81ms
memory: 4328kb

input:

30 9
2
3
2
3
4
8
15
3
5

output:

24

result:

ok single line: '24'
English 繁體中文 简体中文

服务器时间: 2024-11-29 21:43:32 | 开源项目