QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232509#3170. Lunchtime Name Recall8BQube#AC ✓786ms4924kbC++201.9kb2023-10-30 15:43:422023-10-30 15:43:43

Judging History

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

  • [2023-10-30 15:43:43]
  • 评测
  • 测评结果：AC
  • 用时：786ms
  • 内存：4924kb
查看
  • [2023-10-30 15:43:42]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()

set<vector<int>> dp, ndp, done;

void get_dp(int n, int a) {
    //cerr << "get_dp " << a << "\n";
    auto relax = [&](vector<int> mask) {
        /*cerr << "insert ";
        for (int p : mask)
            cerr << p << " ";
        cerr << endl;*/
        sort(ALL(mask));
        ndp.insert(mask);
    };

    for (auto cur : dp) {
        if (done.find(cur) != done.end()) continue;
        done.insert(cur);
        vector<int> nset;
        reverse(ALL(cur));
        auto _dfs = [&](auto dfs, int u, int one, int sum, pii lst) {
            if (u == SZ(cur)) {
                if (one <= sum) 
                    relax(nset);
                return;
            }
            for (int i = max({0, one - (sum - cur[u]), (lst.X == cur[u] ? lst.Y : 0)}); i <= one && i <= cur[u]; ++i) {
                int osz = SZ(nset);
                if (i > 1)
                    nset.pb(i);
                if (cur[u] - i > 1)
                    nset.pb(cur[u] - i);
                dfs(dfs, u + 1, one - i, sum - cur[u], pii(cur[u], i));
                nset.resize(osz);
            }
        };
        _dfs(_dfs, 0, a, n, pii(-1, -1));
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    dp.insert({n});
    while (m--) {
        int a;
        cin >> a;
        ndp.clear();
        get_dp(n, min(a, n - a));
        dp.swap(ndp);
        if (dp.find({}) != dp.end()) break;
    }
    int ans = 0;
    for (auto p : dp) {
        int sum = 0;
        for (int q : p)
            sum += q;
        ans = max(ans, n - sum);
    }
    for (auto p : done) {
        int sum = 0;
        for (int q : p)
            sum += q;
        ans = max(ans, n - sum);
    }
    cout << ans << "\n";
}
源文件, 语言: C++20

详细

Test #1:

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

input:

4 2
2
2

output:

4

result:

ok single line: '4'

Test #2:

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

input:

16 3
6
8
8

output:

5

result:

ok single line: '5'

Test #3:

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

input:

5 2
2
2

output:

3

result:

ok single line: '3'

Test #4:

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

input:

16 3
8
8
8

output:

6

result:

ok single line: '6'

Test #5:

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

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

input:

7 3
3
2
1

output:

4

result:

ok single line: '4'

Test #7:

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

input:

9 4
1
1
3
3

output:

5

result:

ok single line: '5'

Test #8:

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

input:

10 3
4
4
3

output:

6

result:

ok single line: '6'

Test #9:

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

input:

10 3
4
4
5

output:

6

result:

ok single line: '6'

Test #10:

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

input:

10 3
4
4
4

output:

7

result:

ok single line: '7'

Test #11:

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

input:

12 3
6
6
6

output:

6

result:

ok single line: '6'

Test #12:

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

input:

10 5
2
2
2
2
2

output:

7

result:

ok single line: '7'

Test #13:

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

input:

10 6
2
2
2
2
2
2

output:

10

result:

ok single line: '10'

Test #14:

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

input:

10 2
3
3

output:

2

result:

ok single line: '2'

Test #15:

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

input:

10 6
8
5
2
8
8
1

output:

10

result:

ok single line: '10'

Test #16:

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

input:

7 4
5
5
1
2

output:

5

result:

ok single line: '5'

Test #17:

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

input:

2 1
1

output:

2

result:

ok single line: '2'

Test #18:

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

input:

3 1
1

output:

1

result:

ok single line: '1'

Test #19:

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

input:

30 1
15

output:

0

result:

ok single line: '0'

Test #20:

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

input:

3 5
1
1
1
1
1

output:

3

result:

ok single line: '3'

Test #21:

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

input:

5 6
2
2
2
2
2
2

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 483ms
memory: 4268kb

input:

30 5
15
15
15
15
13

output:

28

result:

ok single line: '28'

Test #23:

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

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

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

input:

30 7
9
9
9
9
9
9
2

output:

28

result:

ok single line: '28'

Test #26:

score: 0
Accepted
time: 321ms
memory: 4120kb

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

input:

30 3
2
2
2

output:

4

result:

ok single line: '4'

Test #43:

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

input:

30 6
2
2
2
2
2
2

output:

9

result:

ok single line: '9'

Test #44:

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

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

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

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

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

input:

30 5
15
15
15
15
15

output:

30

result:

ok single line: '30'

Test #49:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

input:

30 5
12
14
15
12
15

output:

27

result:

ok single line: '27'

Test #66:

score: 0
Accepted
time: 533ms
memory: 4868kb

input:

30 5
14
13
15
11
11

output:

26

result:

ok single line: '26'

Test #67:

score: 0
Accepted
time: 622ms
memory: 4808kb

input:

30 5
13
12
14
11
12

output:

26

result:

ok single line: '26'

Test #68:

score: 0
Accepted
time: 451ms
memory: 4736kb

input:

30 6
11
10
9
9
10
9

output:

28

result:

ok single line: '28'

Test #69:

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

input:

30 6
10
7
8
11
9
9

output:

27

result:

ok single line: '27'

Test #70:

score: 0
Accepted
time: 443ms
memory: 4724kb

input:

30 6
7
9
8
10
10
8

output:

26

result:

ok single line: '26'

Test #71:

score: 0
Accepted
time: 196ms
memory: 4660kb

input:

30 7
6
10
7
9
6
8
9

output:

30

result:

ok single line: '30'

Test #72:

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

input:

30 7
7
6
7
10
7
7
10

output:

30

result:

ok single line: '30'

Test #73:

score: 0
Accepted
time: 238ms
memory: 4716kb

input:

30 7
7
8
6
8
8
7
6

output:

28

result:

ok single line: '28'

Test #74:

score: 0
Accepted
time: 202ms
memory: 4180kb

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

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

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

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

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

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

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

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

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

input:

30 9
2
3
2
3
4
8
15
3
5

output:

24

result:

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

服务器时间: 2024-12-02 03:15:14 | 开源项目