QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226888#3170. Lunchtime Name RecallSolitaryDream#AC ✓325ms4824kbC++172.5kb2023-10-26 17:49:442023-10-26 17:49:44

Judging History

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

  • [2023-10-26 17:49:44]
  • 评测
  • 测评结果：AC
  • 用时：325ms
  • 内存：4824kb
查看
  • [2023-10-26 17:49:44]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 32;
inline set<vector<int>> Update(const set<vector<int>> &st, int x, int y) {
    static set<vector<int>> f[N][N];
    set<vector<int>> ans;
    for (auto vec : st) {
        int sm = x + y;
        f[0][x].insert({0});
        for (int k = 0; k < vec.size(); ++k) {
            for (int i = 0; i * 2 <= sm; ++i) {
                int j = sm - i;
                for (auto cur : f[k][i]) {
                    for (int d = 0; d <= vec[k]; ++d) if (d <= i && vec[k] - d <= j) {
                        vector<int> ncur(cur);
                        if (d) ncur.insert(lower_bound(ncur.begin(), ncur.end(), d, greater<int>()), d);
                        if (vec[k] - d) ncur.insert(lower_bound(ncur.begin(), ncur.end(), vec[k] - d, greater<int>()), vec[k] - d);
                        int ni = i - d;
                        if (ni > (sm - vec[k]) - ni) ni = (sm - vec[k]) - ni;
                        f[k + 1][ni].insert(ncur);
                    }
                }
            }
            sm -= vec[k];
        }
        for (auto cur : f[vec.size()][0]) {
            cur.pop_back();
            ans.insert(cur);
        }
        for (int k = 0; k <= vec.size(); ++k)
            for (int i = 0; i <= x; ++i) {
                    f[k][i].clear();
                }
    }
    set<vector<int>> zip_ans;
    for (auto cur: ans) {
        bool flag = 0;
        for (auto x : cur) {
            for (int d = 1; d < x; ++d) {
                vector<int> ncur(cur);
                ncur.erase(lower_bound(ncur.begin(), ncur.end(), x, greater<int>()));
                if (d) ncur.insert(lower_bound(ncur.begin(), ncur.end(), d, greater<int>()), d);
                if (x - d) ncur.insert(lower_bound(ncur.begin(), ncur.end(), x - d, greater<int>()), x - d);
                if (ans.count(ncur)) { flag = 1; break; }
            }
            if (flag) break;
        }
        if (!flag) zip_ans.insert(cur);
    }
    return zip_ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    set<vector<int>> st;
    st.insert({n});
    for (int i = 1, x; i <= m; ++i) {
        cin >> x;
        if (x > n - x) x = n - x;
        st = Update(st, x, n - x);
        // cerr << st.size() << endl;
    }
    int ans = 0;
    for (auto vec : st) {
        int cur = 0;
        while (vec.size() && vec.back() == 1) ++cur, vec.pop_back();
        ans = max(ans, cur);
    }
    printf("%d\n", ans);
    return 0;
}
/*
30 10
15 15 15 15 15
15 15 15 15 15
*/
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

4 2
2
2

output:

4

result:

ok single line: '4'

Test #2:

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

input:

16 3
6
8
8

output:

5

result:

ok single line: '5'

Test #3:

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

input:

5 2
2
2

output:

3

result:

ok single line: '3'

Test #4:

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

input:

16 3
8
8
8

output:

6

result:

ok single line: '6'

Test #5:

score: 0
Accepted
time: 4ms
memory: 3780kb

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: 3744kb

input:

7 3
3
2
1

output:

4

result:

ok single line: '4'

Test #7:

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

input:

9 4
1
1
3
3

output:

5

result:

ok single line: '5'

Test #8:

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

input:

10 3
4
4
3

output:

6

result:

ok single line: '6'

Test #9:

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

input:

10 3
4
4
5

output:

6

result:

ok single line: '6'

Test #10:

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

input:

10 3
4
4
4

output:

7

result:

ok single line: '7'

Test #11:

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

input:

12 3
6
6
6

output:

6

result:

ok single line: '6'

Test #12:

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

input:

10 5
2
2
2
2
2

output:

7

result:

ok single line: '7'

Test #13:

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

input:

10 6
2
2
2
2
2
2

output:

10

result:

ok single line: '10'

Test #14:

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

input:

10 2
3
3

output:

2

result:

ok single line: '2'

Test #15:

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

input:

10 6
8
5
2
8
8
1

output:

10

result:

ok single line: '10'

Test #16:

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

input:

7 4
5
5
1
2

output:

5

result:

ok single line: '5'

Test #17:

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

input:

2 1
1

output:

2

result:

ok single line: '2'

Test #18:

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

input:

3 1
1

output:

1

result:

ok single line: '1'

Test #19:

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

input:

30 1
15

output:

0

result:

ok single line: '0'

Test #20:

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

input:

3 5
1
1
1
1
1

output:

3

result:

ok single line: '3'

Test #21:

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

input:

5 6
2
2
2
2
2
2

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 95ms
memory: 4596kb

input:

30 5
15
15
15
15
13

output:

28

result:

ok single line: '28'

Test #23:

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

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

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: 137ms
memory: 4408kb

input:

30 7
9
9
9
9
9
9
2

output:

28

result:

ok single line: '28'

Test #26:

score: 0
Accepted
time: 79ms
memory: 4588kb

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

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

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: 126ms
memory: 4292kb

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: 70ms
memory: 4356kb

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: 102ms
memory: 4320kb

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: 74ms
memory: 4292kb

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: 101ms
memory: 4360kb

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

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

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: 119ms
memory: 4624kb

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: 3764kb

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: 4060kb

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

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: 35ms
memory: 3956kb

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: 65ms
memory: 4160kb

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: 3660kb

input:

30 3
2
2
2

output:

4

result:

ok single line: '4'

Test #43:

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

input:

30 6
2
2
2
2
2
2

output:

9

result:

ok single line: '9'

Test #44:

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

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: 88ms
memory: 4352kb

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: 72ms
memory: 4072kb

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: 57ms
memory: 4544kb

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: 92ms
memory: 4420kb

input:

30 5
15
15
15
15
15

output:

30

result:

ok single line: '30'

Test #49:

score: 0
Accepted
time: 74ms
memory: 4072kb

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

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: 202ms
memory: 4540kb

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: 173ms
memory: 4424kb

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

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: 279ms
memory: 4464kb

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: 153ms
memory: 4716kb

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: 114ms
memory: 4356kb

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

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: 62ms
memory: 4076kb

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: 213ms
memory: 4444kb

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

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: 224ms
memory: 4680kb

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

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

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: 44ms
memory: 4084kb

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: 277ms
memory: 4824kb

input:

30 5
12
14
15
12
15

output:

27

result:

ok single line: '27'

Test #66:

score: 0
Accepted
time: 282ms
memory: 4464kb

input:

30 5
14
13
15
11
11

output:

26

result:

ok single line: '26'

Test #67:

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

input:

30 5
13
12
14
11
12

output:

26

result:

ok single line: '26'

Test #68:

score: 0
Accepted
time: 212ms
memory: 4764kb

input:

30 6
11
10
9
9
10
9

output:

28

result:

ok single line: '28'

Test #69:

score: 0
Accepted
time: 175ms
memory: 4512kb

input:

30 6
10
7
8
11
9
9

output:

27

result:

ok single line: '27'

Test #70:

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

input:

30 6
7
9
8
10
10
8

output:

26

result:

ok single line: '26'

Test #71:

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

input:

30 7
6
10
7
9
6
8
9

output:

30

result:

ok single line: '30'

Test #72:

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

input:

30 7
7
6
7
10
7
7
10

output:

30

result:

ok single line: '30'

Test #73:

score: 0
Accepted
time: 129ms
memory: 4420kb

input:

30 7
7
8
6
8
8
7
6

output:

28

result:

ok single line: '28'

Test #74:

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

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: 106ms
memory: 4292kb

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: 73ms
memory: 4256kb

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: 136ms
memory: 4400kb

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: 97ms
memory: 4376kb

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: 103ms
memory: 4364kb

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

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

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

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: 64ms
memory: 4340kb

input:

30 9
2
3
2
3
4
8
15
3
5

output:

24

result:

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

Server Time: 2024-11-29 19:56:03 | OpenSource Project