QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#412091#3170. Lunchtime Name RecallohiostatescarletAC ✓1910ms5116kbC++172.2kb2024-05-16 04:35:242024-05-16 04:35:25

Judging History

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

  • [2024-05-16 04:35:25]
  • 评测
  • 测评结果：AC
  • 用时：1910ms
  • 内存：5116kb
查看
  • [2024-05-16 04:35:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define L long long
typedef array<int, 30> A;
void partitions(A&curr, vector<int> out, int i, int split, set<A>&used, set<A>&nex, int last) {
    if (i == 30 || !curr[i]) {
        if (split) return;
        sort(out.begin(), out.end());
        A newA = {0};
        for (int j = 0; j < out.size(); j++) {
            newA[j] = out[j];
        }
        if (!used.count(newA)) {
            // for (int j = 0; j < 30 && curr[j]; j++) cout << curr[j] << " ";
            // cout << "=> ";
            // for (int j = 0; j < 30 && newA[j]; j++) cout << newA[j] << " ";
            // cout << "\n";
            used.insert(newA);
            nex.insert(newA);
        }
    } else {
        int maxSplit = min(split, curr[i]);
        int minSplit = (i > 0 && curr[i] == curr[i-1]) ? last : 0;
        for (int j = minSplit; j <= maxSplit; j++) {
            if (j!=0 && j != curr[i]) {
                out.push_back(j);
                out.push_back(curr[i]-j);
                partitions(curr, out, i+1, split-j, used, nex, j);
                out.pop_back();
                out.pop_back();
            } else {
                out.push_back(curr[i]);
                partitions(curr, out, i+1, split-j, used, nex, j);
                out.pop_back();
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> nums(m,0);
    for (int i = 0; i < m; i++) {
        int v;
        cin >> v;
        nums[i] = min(v, n - v);
    }
    sort(nums.begin(),nums.end());
    A start = {0};
    start[0] = n;
    set<A> used;
    set<A> curr;
    curr.insert(start);
    used.insert(start);
    for (int v : nums) {
        set<A> nex;
        for (auto a = curr.begin(); a != curr.end(); a++) {
            A av = *a;
            partitions(av, vector<int>(), 0, v, used, nex, 0);
        }
        swap(nex, curr);
    }
    int res = 0;
    for (auto a = used.begin(); a != used.end(); a++) {
        int o = 0;
        for (int i = 0; i < 30 && (*a)[i]; i++) {
            if ((*a)[i] == 1) {
                o++;
            }
        }
        res = max(res, o);
    }
    cout << res << '\n';
}
源文件, 语言: C++17

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3876kb

input:

4 2
2
2

output:

4

result:

ok single line: '4'

Test #2:

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

input:

16 3
6
8
8

output:

5

result:

ok single line: '5'

Test #3:

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

input:

5 2
2
2

output:

3

result:

ok single line: '3'

Test #4:

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

input:

16 3
8
8
8

output:

6

result:

ok single line: '6'

Test #5:

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

input:

20 7
1
1
1
1
6
8
8

output:

11

result:

ok single line: '11'

Test #6:

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

input:

7 3
3
2
1

output:

4

result:

ok single line: '4'

Test #7:

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

input:

9 4
1
1
3
3

output:

5

result:

ok single line: '5'

Test #8:

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

input:

10 3
4
4
3

output:

6

result:

ok single line: '6'

Test #9:

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

input:

10 3
4
4
5

output:

6

result:

ok single line: '6'

Test #10:

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

input:

10 3
4
4
4

output:

7

result:

ok single line: '7'

Test #11:

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

input:

12 3
6
6
6

output:

6

result:

ok single line: '6'

Test #12:

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

input:

10 5
2
2
2
2
2

output:

7

result:

ok single line: '7'

Test #13:

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

input:

10 6
2
2
2
2
2
2

output:

10

result:

ok single line: '10'

Test #14:

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

input:

10 2
3
3

output:

2

result:

ok single line: '2'

Test #15:

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

input:

10 6
8
5
2
8
8
1

output:

10

result:

ok single line: '10'

Test #16:

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

input:

7 4
5
5
1
2

output:

5

result:

ok single line: '5'

Test #17:

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

input:

2 1
1

output:

2

result:

ok single line: '2'

Test #18:

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

input:

3 1
1

output:

1

result:

ok single line: '1'

Test #19:

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

input:

30 1
15

output:

0

result:

ok single line: '0'

Test #20:

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

input:

3 5
1
1
1
1
1

output:

3

result:

ok single line: '3'

Test #21:

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

input:

5 6
2
2
2
2
2
2

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 1636ms
memory: 4668kb

input:

30 5
15
15
15
15
13

output:

28

result:

ok single line: '28'

Test #23:

score: 0
Accepted
time: 609ms
memory: 4112kb

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: 457ms
memory: 4124kb

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: 711ms
memory: 4720kb

input:

30 7
9
9
9
9
9
9
2

output:

28

result:

ok single line: '28'

Test #26:

score: 0
Accepted
time: 941ms
memory: 4228kb

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: 475ms
memory: 4452kb

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: 1514ms
memory: 4976kb

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: 475ms
memory: 4452kb

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: 91ms
memory: 4368kb

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: 430ms
memory: 4324kb

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: 391ms
memory: 4288kb

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: 658ms
memory: 4208kb

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: 411ms
memory: 4536kb

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: 384ms
memory: 4300kb

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: 483ms
memory: 4396kb

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: 0ms
memory: 3632kb

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: 1ms
memory: 3592kb

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: 3ms
memory: 3924kb

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: 26ms
memory: 3900kb

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: 86ms
memory: 4204kb

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: 0ms
memory: 3876kb

input:

30 3
2
2
2

output:

4

result:

ok single line: '4'

Test #43:

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

input:

30 6
2
2
2
2
2
2

output:

9

result:

ok single line: '9'

Test #44:

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

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: 107ms
memory: 4228kb

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: 89ms
memory: 4196kb

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: 289ms
memory: 4040kb

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: 1392ms
memory: 4752kb

input:

30 5
15
15
15
15
15

output:

30

result:

ok single line: '30'

Test #49:

score: 0
Accepted
time: 161ms
memory: 4544kb

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: 206ms
memory: 4244kb

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: 1121ms
memory: 4868kb

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: 712ms
memory: 5004kb

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: 795ms
memory: 4832kb

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: 1440ms
memory: 4848kb

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: 762ms
memory: 4776kb

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: 182ms
memory: 4108kb

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: 267ms
memory: 4552kb

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: 162ms
memory: 4232kb

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: 485ms
memory: 4092kb

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: 564ms
memory: 4332kb

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: 524ms
memory: 4156kb

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: 468ms
memory: 4148kb

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: 501ms
memory: 4140kb

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: 648ms
memory: 4200kb

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: 1864ms
memory: 5036kb

input:

30 5
12
14
15
12
15

output:

27

result:

ok single line: '27'

Test #66:

score: 0
Accepted
time: 1910ms
memory: 4820kb

input:

30 5
14
13
15
11
11

output:

26

result:

ok single line: '26'

Test #67:

score: 0
Accepted
time: 1786ms
memory: 4912kb

input:

30 5
13
12
14
11
12

output:

26

result:

ok single line: '26'

Test #68:

score: 0
Accepted
time: 1032ms
memory: 5088kb

input:

30 6
11
10
9
9
10
9

output:

28

result:

ok single line: '28'

Test #69:

score: 0
Accepted
time: 1084ms
memory: 5116kb

input:

30 6
10
7
8
11
9
9

output:

27

result:

ok single line: '27'

Test #70:

score: 0
Accepted
time: 1001ms
memory: 4888kb

input:

30 6
7
9
8
10
10
8

output:

26

result:

ok single line: '26'

Test #71:

score: 0
Accepted
time: 779ms
memory: 4840kb

input:

30 7
6
10
7
9
6
8
9

output:

30

result:

ok single line: '30'

Test #72:

score: 0
Accepted
time: 796ms
memory: 4892kb

input:

30 7
7
6
7
10
7
7
10

output:

30

result:

ok single line: '30'

Test #73:

score: 0
Accepted
time: 549ms
memory: 4704kb

input:

30 7
7
8
6
8
8
7
6

output:

28

result:

ok single line: '28'

Test #74:

score: 0
Accepted
time: 322ms
memory: 4068kb

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: 448ms
memory: 4336kb

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: 249ms
memory: 4248kb

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: 288ms
memory: 4488kb

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: 406ms
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: 249ms
memory: 4332kb

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: 394ms
memory: 4468kb

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: 300ms
memory: 4380kb

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: 263ms
memory: 4404kb

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: 870ms
memory: 4212kb

input:

30 9
2
3
2
3
4
8
15
3
5

output:

24

result:

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

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