QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#203397#2481. Pickpocketssalvator_noster#TL 95ms13784kbC++202.6kb2023-10-06 17:12:032023-10-06 17:12:03

Judging History

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

  • [2023-10-06 17:12:03]
  • 评测
  • 测评结果：TL
  • 用时：95ms
  • 内存：13784kb
查看
  • [2023-10-06 17:12:03]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef map <int, int> mi;

const int MAX_N = 100000 + 5;
const int INF32 = 0x3f3f3f3f;
const int lim = 20000000;

int N, M, c[MAX_N], l[MAX_N], cost[MAX_N];
mi a;
int totlen[MAX_N], totcost[MAX_N];
map <pair <mi, int>, int> f;
set <pair <int, int>> candidate;
int Time = 0;

void add(mi &a, int pos) {
    if (a.count(pos)) {
        if (!++ a[pos]) a.erase(pos);
    }else a[pos] = 1;
}

void sub(mi &a, int pos) {
    if (a.count(pos)) {
        if (!-- a[pos]) {
            a.erase(pos);
        }
    }else {
        a[pos] = -1;
    }
}

void debug(mi &x) {
    for (auto [pos, cnt] : x) fprintf(stderr, "pos = %d, cnt = %d\n", pos, cnt);
}

int dfs(mi &cura, int status, int tot) {
    // debug(cura);
    // fprintf(stderr, "status = %d\n", status);
    Time ++;
    if (Time > lim) {
        printf("0\n");
        exit(0);
    }
    if (cura.empty()) return 1;
    pair <mi, int> tmp = make_pair(cura, status);
    if (f.count(tmp)) return f[tmp];
    f[tmp] = 0;
    int sum = 0;
    for (auto [pos, cnt] : cura) {
        if (cnt > 0) {
            sum += cnt;
            if (sum > tot) break;
        }
    }
    if (sum > tot) return 0;
    auto x = *cura.begin();
    if (x.second < 0) return 0;
    else {
        sub(cura, x.first);
        // cura.erase(cura.begin());
        // if (-- x.second) cura.insert(x);
    }
    int S = status;
    while (S) {
        int ctz = __builtin_ctz(S);
        if (x.first + l[ctz] <= N + 1) {
            add(cura, x.first + l[ctz]);
            if (dfs(cura, status ^ 1 << ctz, tot - 1)) return f[tmp] = 1;
            sub(cura, x.first + l[ctz]);
        }
        S ^= (1 << ctz);
    }
    add(cura, x.first);
    return 0;
}

int main() {
    scanf("%d%d", &N, &M);
    ll sumC = 0;
    for (int i = 1; i <= N; i ++) {
        scanf("%d", c + i);
        sumC += c[i];
        if (c[i] != c[i - 1]) a[i] = c[i] - c[i - 1];
    }
    if (c[N]) a[N + 1] = -c[N];
    for (int i = 0; i < M; i ++) {
        scanf("%d%d", l + i, cost + i);
    }
    int ans = 0;
    for (int s = 1; s < (1 << M); s ++) {
        int ctz = __builtin_ctz(s);
        totlen[s] = totlen[s ^ (1 << ctz)] + l[ctz];
        totcost[s] = totcost[s ^ (1 << ctz)] + cost[ctz];
        if (sumC == totlen[s]) {
            candidate.insert(make_pair(-totcost[s], s));
        }
    }
    for (auto x : candidate) {
        if (dfs(a, x.second, __builtin_popcount(x.second))) {
            ans = -x.first; break;
        }
    }
    printf("%d\n", ans);
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

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

input:

2 2
1 2
1 5
2 5

output:

10

result:

ok single line: '10'

Test #2:

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

input:

2 2
1 2
2 5
1 5

output:

10

result:

ok single line: '10'

Test #3:

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

input:

3 4
2 1 2
3 2
1 1
1 2
1 3

output:

7

result:

ok single line: '7'

Test #4:

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

input:

1 5
2
1 2
1 5
1 3
1 5
1 3

output:

10

result:

ok single line: '10'

Test #5:

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

input:

1 5
1
1 2
1 1
1 2
1 5
1 2

output:

5

result:

ok single line: '5'

Test #6:

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

input:

1 7
0
1 5
1 5
1 5
1 2
1 5
1 3
1 6

output:

0

result:

ok single line: '0'

Test #7:

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

input:

3 6
2 1 1
2 1
3 5
2 3
3 3
2 4
3 3

output:

0

result:

ok single line: '0'

Test #8:

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

input:

2 5
1 1
1 5
2 4
1 4
2 2
1 1

output:

9

result:

ok single line: '9'

Test #9:

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

input:

1 2
1
1 5
1 4

output:

5

result:

ok single line: '5'

Test #10:

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

input:

2 4
0 1
1 6
2 2
2 5
2 5

output:

6

result:

ok single line: '6'

Test #11:

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

input:

3 5
0 0 0
3 2
3 1
3 1
1 3
1 5

output:

0

result:

ok single line: '0'

Test #12:

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

input:

3 6
0 1 0
3 3
1 3
1 2
1 2
1 3
3 2

output:

3

result:

ok single line: '3'

Test #13:

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

input:

2 7
2 0
2 2
1 6
2 4
1 6
1 6
1 2
2 6

output:

12

result:

ok single line: '12'

Test #14:

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

input:

2 6
0 3
2 3
2 16
1 12
2 10
1 16
1 8

output:

36

result:

ok single line: '36'

Test #15:

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

input:

3 13
4 0 3
1 19
3 12
1 13
2 19
1 18
3 4
3 10
1 13
1 19
2 10
3 15
1 20
3 5

output:

0

result:

ok single line: '0'

Test #16:

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

input:

4 2
3 2 4 0
4 10
3 14

output:

0

result:

ok single line: '0'

Test #17:

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

input:

4 6
3 1 3 1
4 9
4 18
1 15
3 15
2 6
1 19

output:

0

result:

ok single line: '0'

Test #18:

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

input:

3 14
3 0 1
3 16
3 7
3 9
3 11
3 15
3 15
2 16
1 1
2 18
3 16
3 13
3 11
1 4
3 4

output:

0

result:

ok single line: '0'

Test #19:

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

input:

2 9
3 1
1 18
1 15
1 15
1 4
2 17
1 4
2 1
1 15
2 16

output:

63

result:

ok single line: '63'

Test #20:

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

input:

1 9
2
1 5
1 11
1 20
1 10
1 10
1 11
1 9
1 8
1 19

output:

39

result:

ok single line: '39'

Test #21:

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

input:

4 7
1 0 0 2
4 15
4 18
2 8
2 2
2 6
3 11
3 11

output:

0

result:

ok single line: '0'

Test #22:

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

input:

2 2
2 3
2 6
1 1

output:

0

result:

ok single line: '0'

Test #23:

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

input:

1 15
4
1 2
1 12
1 7
1 5
1 13
1 10
1 7
1 5
1 1
1 18
1 9
1 5
1 17
1 9
1 6

output:

60

result:

ok single line: '60'

Test #24:

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

input:

4 14
4 4 0 4
4 20
2 13
2 4
1 20
3 4
4 6
3 9
2 8
1 19
3 14
2 18
2 18
1 15
1 19

output:

130

result:

ok single line: '130'

Test #25:

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

input:

2 5
0 0
1 16
2 20
1 16
2 3
2 11

output:

0

result:

ok single line: '0'

Test #26:

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

input:

2 8
4 0
2 7
1 20
2 10
2 17
1 17
1 17
1 15
2 20

output:

69

result:

ok single line: '69'

Test #27:

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

input:

4 12
4 1 2 1
1 17
3 18
4 19
1 7
4 19
3 19
1 6
1 18
2 3
3 17
1 9
3 4

output:

76

result:

ok single line: '76'

Test #28:

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

input:

1 14
2
1 13
1 15
1 17
1 9
1 1
1 15
1 9
1 18
1 13
1 4
1 20
1 11
1 18
1 18

output:

38

result:

ok single line: '38'

Test #29:

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

input:

4 8
4 0 4 3
4 16
4 13
1 6
1 12
4 10
3 19
4 16
3 6

output:

0

result:

ok single line: '0'

Test #30:

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

input:

2 6
0 3
2 8
2 2
2 13
2 15
1 19
1 9

output:

0

result:

ok single line: '0'

Test #31:

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

input:

5 13
3 1 4 1 0
2 5
3 1
5 12
5 9
4 13
5 1
2 6
3 6
2 8
2 15
4 5
1 8
3 12

output:

0

result:

ok single line: '0'

Test #32:

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

input:

4 9
3 2 4 3
4 14
4 10
4 11
1 14
4 8
3 17
4 12
3 9
3 9

output:

0

result:

ok single line: '0'

Test #33:

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

input:

2 15
1 0
2 4
2 17
2 4
2 4
1 7
2 10
1 9
1 8
2 20
1 1
2 9
1 6
1 17
2 15
2 4

output:

17

result:

ok single line: '17'

Test #34:

score: 0
Accepted
time: 17ms
memory: 9436kb

input:

100000 16
14443 55420 45271 59540 17506 45279 49513 7118 52062 23449 62240 81654 47001 82704 81577 90132 54258 108 41873 82899 73494 8454 43677 34844 92634 48581 7109 1530 89551 44235 82584 49481 69802 20448 78330 70257 67421 71672 45574 96521 64524 43129 33599 37095 57123 69486 6307 74558 9699 1494...

output:

0

result:

ok single line: '0'

Test #35:

score: 0
Accepted
time: 22ms
memory: 9472kb

input:

100000 16
34132 25992 9700 90156 37155 60117 91934 19647 21415 98451 85854 51164 39403 80732 68947 34179 10383 43258 89748 79195 49897 93439 99072 84649 3567 21423 59855 21175 31153 43214 81799 35873 50482 75563 11972 64395 85329 14962 60476 19670 77437 86503 26544 26505 97938 98378 18263 91959 1093...

output:

0

result:

ok single line: '0'

Test #36:

score: 0
Accepted
time: 21ms
memory: 9736kb

input:

100000 16
49337 49202 98923 88065 90751 42204 62277 46326 94035 61743 11491 18245 67892 65458 14981 83057 23342 60570 53140 91901 61983 77500 5364 30637 59391 20822 7992 68913 25963 56681 75276 54999 95145 6833 64626 37669 49186 62351 47235 26430 2217 29040 8409 79387 68362 31357 19385 15922 24388 2...

output:

0

result:

ok single line: '0'

Test #37:

score: 0
Accepted
time: 22ms
memory: 9720kb

input:

100000 16
100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 100000 0 10...

output:

0

result:

ok single line: '0'

Test #38:

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

input:

1 16
16
1 813962
1 261224
1 292357
1 26638
1 342500
1 220901
1 329926
1 283296
1 444155
1 512333
1 670909
1 546612
1 398289
1 243805
1 299229
1 241034

output:

5927170

result:

ok single line: '5927170'

Test #39:

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

input:

1 16
16
1 559357
1 192158
1 650434
1 120360
1 505929
1 98087
1 596733
1 565702
1 460486
1 797314
1 77027
1 569947
1 799522
1 791499
1 794206
1 658821

output:

8237582

result:

ok single line: '8237582'

Test #40:

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

input:

12 16
1 1 1 1 1 1 1 1 1 1 1 1
12 3
10 2
3 9
9 2
3 9
3 10
7 1
8 2
2 4
9 5
12 11
7 3
12 4
5 6
6 7
12 6

output:

26

result:

ok single line: '26'

Test #41:

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

input:

12 16
1 1 1 1 1 1 1 1 1 1 1 1
10 9
7 8
4 3
7 7
3 6
9 2
1 7
1 10
12 10
2 4
3 10
2 3
4 9
8 6
8 11
9 7

output:

42

result:

ok single line: '42'

Test #42:

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

input:

10 16
1 1 1 1 1 1 1 1 1 1
3 8
3 9
8 11
3 7
2 10
6 3
10 3
9 4
8 11
8 6
10 7
8 2
5 10
1 3
7 2
10 10

output:

29

result:

ok single line: '29'

Test #43:

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

input:

18 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
9 9
1 4
4 3
6 6
16 3
13 6
2 3
7 5
8 4
12 4
12 6
11 3
11 3
16 1
5 4
10 2

output:

22

result:

ok single line: '22'

Test #44:

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

input:

20 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
11 1
3 1
4 3
14 5
7 6
10 4
11 1
17 2
8 8
3 9
8 9
5 6
10 11
17 8
8 6
3 7

output:

30

result:

ok single line: '30'

Test #45:

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

input:

7 16
1 1 1 1 1 1 1
4 9
6 11
4 6
3 11
5 1
5 3
7 9
6 8
2 10
5 5
7 1
5 4
2 10
5 9
5 7
5 11

output:

31

result:

ok single line: '31'

Test #46:

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

input:

10 16
1 1 1 1 1 1 1 1 1 1
6 5
1 11
3 1
3 10
10 9
10 11
5 9
8 7
8 2
4 1
4 11
10 9
9 5
8 11
6 1
8 1

output:

31

result:

ok single line: '31'

Test #47:

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

input:

20 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 2
9 7
20 8
1 3
10 7
18 9
10 9
16 7
20 9
12 11
3 8
4 6
3 2
2 9
13 5
17 2

output:

35

result:

ok single line: '35'

Test #48:

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

input:

2 16
1 1
1 11
2 7
1 8
1 8
2 4
1 3
2 8
2 7
1 4
1 2
2 11
1 2
2 11
1 11
1 5
1 11

output:

22

result:

ok single line: '22'

Test #49:

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

input:

4 16
1 1 1 1
1 6
3 4
4 8
2 3
2 11
4 3
4 9
1 6
3 5
3 10
2 1
1 4
3 4
1 1
3 2
3 5

output:

23

result:

ok single line: '23'

Test #50:

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

input:

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

output:

34

result:

ok single line: '34'

Test #51:

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

input:

20 16
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
11 10
17 11
3 11
2 4
6 4
13 9
11 3
4 11
16 8
4 4
20 1
8 9
2 6
12 11
19 6
19 5

output:

59

result:

ok single line: '59'

Test #52:

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

input:

18 16
3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3
9 11
13 7
4 1
8 1
10 9
13 9
14 2
7 8
14 6
17 5
9 6
17 2
12 6
8 7
3 8
3 2

output:

50

result:

ok single line: '50'

Test #53:

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

input:

10 16
4 4 4 4 4 4 4 4 4 4
10 11
10 2
1 5
1 5
9 11
9 4
9 7
5 9
1 8
3 11
6 6
5 5
2 3
6 1
8 2
7 11

output:

74

result:

ok single line: '74'

Test #54:

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

input:

15 16
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5
9 2
2 6
11 8
1 4
13 11
1 3
14 4
13 3
7 8
6 6
6 6
13 11
5 1
6 5
4 4
8 9

output:

72

result:

ok single line: '72'

Test #55:

score: -100
Time Limit Exceeded

input:

20 16
6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6
2 9
8 11
10 6
13 4
7 3
16 5
19 8
14 2
3 6
16 8
2 6
20 9
16 5
10 5
12 9
8 4

output:

result:
English 繁體中文 简体中文

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