QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#301510	#6372. Dance	SolitaryDream	WA	395ms	11448kb	C++14	2.7kb	2024-01-10 00:21:59	2024-01-10 00:21:59

Judging History

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

[2024-01-10 00:21:59]
评测

测评结果：WA
用时：395ms
内存：11448kb

查看

[2024-01-10 00:21:59]
提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 500;
int n, d, a, b;
bool req[N];
inline int Calc(int x, int y) {
    if (x == 0 && y == 1) return a;
    else if (y == 1) return min(a, b);
    else return 0;
}
void Solve1() {
    static int f[2][1 << 21];
    for (int i = 1; i < (1 << d + 1); ++i) f[0][i] = 1e9;
    f[0][0] = 0;
    for (int i = 0; i < 200; ++i) {
        int ni = (i + 1) & 1;
        for (int j = 0; j < (1 << d + 1); ++j) f[ni][j] = 1e9;
        // put on i+1
        for (int j = 0; j < (1 << d + 1); ++j) {
            // put on i+1
            int nf = f[i & 1][j] + Calc(j & 1, 1);
            int nj = j >> 1 | 1;
            f[ni][nj] = min(f[ni][nj], nf);
            // not put on i + 1
            if (~j >> 1 & 1) {
                int nf = f[i & 1][j] + Calc(j & 1, 0);
                int nj = j >> 1 | (req[i] << d);
                f[ni][nj] = min(f[ni][nj], nf);
            }
        }
    }
    cout << f[200 & 1][0] << endl;
}
inline void Solve2() {
    static int f[2][1 << 10];
    int num = (200 + d - 1) / d;
    int ans = 1e9;
    for (int st = 0; st < (1 << num); st += 1) {
        bool flag = 0;
        for (int i = 0; i < num; ++i) {
            int pos = i * d + 1;
            if (req[pos] && (st >> i & 1) == 0 && (st >> i + 1 & 1) == 0) flag = 1;
        }
        if (flag) continue;
        int cur = 0;
        for (int i = 0; i < (1 << num); ++i) f[cur][i] = 1e9;
        f[cur][st & ~(1 << num)] = 0;
        for (int delta = 1; delta < d; ++delta) {
            for (int i = 0; i < num; ++i) {
                for (int j = 0; j < (1 << num); ++j) f[!cur][j] = 1e9;
                for (int j = 0; j < (1 << num); ++j) {
                    int pos = i * d + delta + 1;
                    int nj = j | (1 << i);
                    f[!cur][nj] = min(f[!cur][nj], f[cur][j] + Calc(j >> i & 1, 1) + (delta + 1 == d) * Calc(1, st >> (i + 1) & 1));
                    if (pos - d >= 0 && req[pos - d] && (j >> (i - 1) & 1) == 0) continue;
                    if (pos + d > 200 && req[pos]) continue;
                    nj = j & ~(1 << i);
                    f[!cur][nj] = min(f[!cur][nj], f[cur][j] + Calc(j >> i & 1, 0) + (delta + 1 == d) * Calc(0, st >> (i + 1) & 1));
                }
                cur ^= 1;
            }
        }
        for (int i = 0; i < (1 << num); ++i) ans = min(ans, f[cur][i]);
    }
    cout << ans << endl;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> d >> a >> b;
    d *= 2;
    for (int i = 1, x; i <= n; ++i) {
        cin >> x;
        req[x] = 1;
    }
    if (d <= 20) {
        Solve1();
    } else {
        Solve2();
    }
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 5556kb

input:

3 1 2 1
4 1 7

output:

result:

ok 1 number(s): "5"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5732kb

input:

3 1 7 1
4 1 7

output:

result:

ok 1 number(s): "11"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5672kb

input:

1 1 441060 865580
6

output:

result:

ok 1 number(s): "441060"

Test #4:

score: 0

Accepted

time: 1ms

memory: 5756kb

input:

1 2 524484 157528
88

output:

result:

ok 1 number(s): "524484"

Test #5:

score: 0

Accepted

time: 0ms

memory: 5764kb

input:

1 3 607908 706373
65

output:

result:

ok 1 number(s): "607908"

Test #6:

score: 0

Accepted

time: 0ms

memory: 5676kb

input:

1 1 724036 287921
39

output:

result:

ok 1 number(s): "724036"

Test #7:

score: 0

Accepted

time: 1ms

memory: 5668kb

input:

1 4 807460 804061
17

output:

result:

ok 1 number(s): "807460"

Test #8:

score: 0

Accepted

time: 11ms

memory: 5800kb

input:

1 7 974308 869046
72

output:

result:

ok 1 number(s): "974308"

Test #9:

score: 0

Accepted

time: 1ms

memory: 5676kb

input:

1 4 221588 389967
17

output:

result:

ok 1 number(s): "221588"

Test #10:

score: 0

Accepted

time: 180ms

memory: 11448kb

input:

1 9 704116 877292
5

output:

result:

ok 1 number(s): "704116"

Test #11:

score: 0

Accepted

time: 1ms

memory: 5712kb

input:

1 3 820703 814856
86

output:

result:

ok 1 number(s): "820703"

Test #12:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

1 29 195626 207042
54

output:

result:

ok 1 number(s): "195626"

Test #13:

score: 0

Accepted

time: 0ms

memory: 3644kb

input:

1 19 794740 856124
14

output:

result:

ok 1 number(s): "794740"

Test #14:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

1 28 444117 184242
58

output:

result:

ok 1 number(s): "444117"

Test #15:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

1 32 527541 733087
27

output:

result:

ok 1 number(s): "527541"

Test #16:

score: 0

Accepted

time: 1ms

memory: 3660kb

input:

1 21 610965 281931
9

output:

result:

ok 1 number(s): "610965"

Test #17:

score: 0

Accepted

time: 11ms

memory: 5848kb

input:

1 7 393855 215606
79

output:

result:

ok 1 number(s): "393855"

Test #18:

score: 0

Accepted

time: 1ms

memory: 5752kb

input:

2 1 228470 977748
3 41

output:

result:

ok 1 number(s): "456940"

Test #19:

score: 0

Accepted

time: 1ms

memory: 5620kb

input:

2 2 344598 526593
80 2

output:

result:

ok 1 number(s): "689196"

Test #20:

score: 0

Accepted

time: 1ms

memory: 5680kb

input:

2 2 428022 42733
62 56

output:

result:

ok 1 number(s): "513488"

Test #21:

score: 0

Accepted

time: 1ms

memory: 5624kb

input:

2 2 511446 591577
28 9

output:

result:

ok 1 number(s): "1022892"

Test #22:

score: 0

Accepted

time: 1ms

memory: 5676kb

input:

2 1 594870 883526
5 67

output:

result:

ok 1 number(s): "1189740"

Test #23:

score: 0

Accepted

time: 1ms

memory: 5684kb

input:

2 2 794422 13919
65 74

output:

result:

ok 1 number(s): "864017"

Test #24:

score: 0

Accepted

time: 0ms

memory: 5624kb

input:

2 1 883770 771924
1 15

output:

result:

ok 1 number(s): "1767540"

Test #25:

score: 0

Accepted

time: 1ms

memory: 5620kb

input:

2 1 333594 259250
89 95

output:

result:

ok 1 number(s): "667188"

Test #26:

score: 0

Accepted

time: 391ms

memory: 3592kb

input:

2 11 482884 164110
69 4

output:

result:

ok 1 number(s): "965768"

Test #27:

score: 0

Accepted

time: 20ms

memory: 3680kb

input:

2 14 49295 556296
29 97

output:

result:

ok 1 number(s): "98590"

Test #28:

score: 0

Accepted

time: 100ms

memory: 3632kb

input:

2 12 424218 948481
98 86

output:

result:

ok 1 number(s): "848436"

Test #29:

score: 0

Accepted

time: 0ms

memory: 3572kb

input:

2 17 73594 533496
33 77

output:

result:

ok 1 number(s): "147188"

Test #30:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

2 25 157018 49636
15 38

output:

result:

ok 1 number(s): "314036"

Test #31:

score: 0

Accepted

time: 392ms

memory: 3572kb

input:

2 11 273146 631185
92 92

output:

result:

ok 1 number(s): "273146"

Test #32:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

2 34 23333 340667
58 79

output:

result:

ok 1 number(s): "46666"

Test #33:

score: 0

Accepted

time: 0ms

memory: 5620kb

input:

3 1 791688 281405
92 12 7

output:

result:

ok 1 number(s): "2375064"

Test #34:

score: 0

Accepted

time: 1ms

memory: 5676kb

input:

3 1 907816 606057
73 61 76

output:

result:

ok 1 number(s): "2421689"

Test #35:

score: 0

Accepted

time: 1ms

memory: 5600kb

input:

3 2 991240 154901
43 23 53

output:

result:

ok 1 number(s): "2911886"

Test #36:

score: 0

Accepted

time: 0ms

memory: 5680kb

input:

3 2 107368 703746
20 76 30

output:

result:

ok 1 number(s): "322104"

Test #37:

score: 0

Accepted

time: 1ms

memory: 5624kb

input:

3 5 158088 252590
2 30 94

output:

result:

ok 1 number(s): "474264"

Test #38:

score: 0

Accepted

time: 0ms

memory: 5708kb

input:

3 5 390344 317575
61 41 44

output:

result:

ok 1 number(s): "1171032"

Test #39:

score: 0

Accepted

time: 4ms

memory: 9716kb

input:

3 6 513247 896986
88 3 16

output:

result:

ok 1 number(s): "1539741"

Test #40:

score: 0

Accepted

time: 8ms

memory: 3688kb

input:

3 15 963072 384312
72 83 85

output:

result:

ok 1 number(s): "2694768"

Test #41:

score: 0

Accepted

time: 100ms

memory: 3640kb

input:

3 12 112362 513363
44 96 5

output:

result:

ok 1 number(s): "337086"

Test #42:

score: 0

Accepted

time: 1ms

memory: 3588kb

input:

3 20 711477 872845
13 85 98

output:

result:

ok 1 number(s): "2134431"

Test #43:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

3 29 310592 297735
69 74 90

output:

result:

ok 1 number(s): "931776"

Test #44:

score: 0

Accepted

time: 98ms

memory: 3668kb

input:

3 12 959968 882750
20 65 8

output:

result:

ok 1 number(s): "2879904"

Test #45:

score: 0

Accepted

time: 2ms

memory: 3676kb

input:

3 18 43392 431594
94 22 73

output:

result:

ok 1 number(s): "130176"

Test #46:

score: 0

Accepted

time: 395ms

memory: 3576kb

input:

3 11 126816 756246
68 76 50

output:

result:

ok 1 number(s): "380448"

Test #47:

score: 0

Accepted

time: 0ms

memory: 3640kb

input:

3 49 685514 689921
41 59 83

output:

result:

ok 1 number(s): "2056542"

Test #48:

score: 0

Accepted

time: 1ms

memory: 5628kb

input:

10 1 251127 64273
86 86 27 41 99 63 58 16 98 14

output:

result:

ok 1 number(s): "1763854"

Test #49:

score: 0

Accepted

time: 1ms

memory: 5608kb

input:

10 2 334552 580414
67 40 92 25 91 27 40 56 42 4

output:

result:

ok 1 number(s): "3010968"

Test #50:

score: 0

Accepted

time: 1ms

memory: 5612kb

input:

10 3 417976 905066
45 1 69 100 75 82 22 99 85 94

output:

result:

ok 1 number(s): "3343808"

Test #51:

score: 0

Accepted

time: 1ms

memory: 5732kb

input:

10 1 534104 453910
19 55 41 83 59 38 4 39 25 85

output:

result:

ok 1 number(s): "4192638"

Test #52:

score: 0

Accepted

time: 1ms

memory: 5656kb

input:

10 1 617528 2755
96 4 10 67 47 97 87 83 69 83

output:

result:

ok 1 number(s): "868233"

Test #53:

score: 0

Accepted

time: 3ms

memory: 5752kb

input:

10 6 784376 67739
51 19 60 25 23 16 51 66 64 68

output:

result:

ok 1 number(s): "2652576"

Test #54:

score: 0

Accepted

time: 0ms

memory: 5628kb

input:

10 3 624048 730227
9 22 29 1 17 18 86 58 63 47

output:

result:

ok 1 number(s): "6240480"

Test #55:

score: -100

Wrong Answer

time: 15ms

memory: 3664kb

input:

10 14 73873 217553
97 98 93 1 57 8 93 72 86 6

output:

result:

wrong answer 1st numbers differ - expected: '664857', found: '590984'