QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#301507	#6372. Dance	SolitaryDream	WA	182ms	11768kb	C++14	2.7kb	2024-01-10 00:07:12	2024-01-10 00:07:13

Judging History

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

[2024-01-10 00:07:13]
评测

测评结果：WA
用时：182ms
内存：11768kb

查看

[2024-01-10 00:07:12]
提交

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;
    int ans = 1e9;
    for (int st = 0; st < (1 << num + 1); st += 2) {
        bool flag = 0;
        for (int i = 0; i < num; ++i) {
            int pos = i * d;
            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 = 0; delta + 1 < 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 - 1) * 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 - 1) * 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;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 5616kb

input:

3 1 2 1
4 1 7

output:

result:

ok 1 number(s): "5"

Test #2:

score: 0

Accepted

time: 1ms

memory: 5616kb

input:

3 1 7 1
4 1 7

output:

result:

ok 1 number(s): "11"

Test #3:

score: 0

Accepted

time: 1ms

memory: 5676kb

input:

1 1 441060 865580
6

output:

result:

ok 1 number(s): "441060"

Test #4:

score: 0

Accepted

time: 1ms

memory: 5704kb

input:

1 2 524484 157528
88

output:

result:

ok 1 number(s): "524484"

Test #5:

score: 0

Accepted

time: 1ms

memory: 5624kb

input:

1 3 607908 706373
65

output:

result:

ok 1 number(s): "607908"

Test #6:

score: 0

Accepted

time: 0ms

memory: 5700kb

input:

1 1 724036 287921
39

output:

result:

ok 1 number(s): "724036"

Test #7:

score: 0

Accepted

time: 1ms

memory: 5628kb

input:

1 4 807460 804061
17

output:

result:

ok 1 number(s): "807460"

Test #8:

score: 0

Accepted

time: 11ms

memory: 5748kb

input:

1 7 974308 869046
72

output:

result:

ok 1 number(s): "974308"

Test #9:

score: 0

Accepted

time: 0ms

memory: 5712kb

input:

1 4 221588 389967
17

output:

result:

ok 1 number(s): "221588"

Test #10:

score: 0

Accepted

time: 182ms

memory: 11768kb

input:

1 9 704116 877292
5

output:

result:

ok 1 number(s): "704116"

Test #11:

score: 0

Accepted

time: 1ms

memory: 5620kb

input:

1 3 820703 814856
86

output:

result:

ok 1 number(s): "820703"

Test #12:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

1 29 195626 207042
54

output:

result:

ok 1 number(s): "195626"

Test #13:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

1 19 794740 856124
14

output:

result:

ok 1 number(s): "794740"

Test #14:

score: 0

Accepted

time: 0ms

memory: 3620kb

input:

1 28 444117 184242
58

output:

result:

ok 1 number(s): "444117"

Test #15:

score: 0

Accepted

time: 0ms

memory: 3664kb

input:

1 32 527541 733087
27

output:

result:

ok 1 number(s): "527541"

Test #16:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

1 21 610965 281931
9

output:

result:

ok 1 number(s): "610965"

Test #17:

score: 0

Accepted

time: 9ms

memory: 9872kb

input:

1 7 393855 215606
79

output:

result:

ok 1 number(s): "393855"

Test #18:

score: 0

Accepted

time: 1ms

memory: 5712kb

input:

2 1 228470 977748
3 41

output:

result:

ok 1 number(s): "456940"

Test #19:

score: 0

Accepted

time: 1ms

memory: 5708kb

input:

2 2 344598 526593
80 2

output:

result:

ok 1 number(s): "689196"

Test #20:

score: 0

Accepted

time: 1ms

memory: 5624kb

input:

2 2 428022 42733
62 56

output:

result:

ok 1 number(s): "513488"

Test #21:

score: 0

Accepted

time: 1ms

memory: 5704kb

input:

2 2 511446 591577
28 9

output:

result:

ok 1 number(s): "1022892"

Test #22:

score: 0

Accepted

time: 1ms

memory: 5716kb

input:

2 1 594870 883526
5 67

output:

result:

ok 1 number(s): "1189740"

Test #23:

score: 0

Accepted

time: 1ms

memory: 5660kb

input:

2 2 794422 13919
65 74

output:

result:

ok 1 number(s): "864017"

Test #24:

score: 0

Accepted

time: 1ms

memory: 5668kb

input:

2 1 883770 771924
1 15

output:

result:

ok 1 number(s): "1767540"

Test #25:

score: 0

Accepted

time: 1ms

memory: 5760kb

input:

2 1 333594 259250
89 95

output:

result:

ok 1 number(s): "667188"

Test #26:

score: 0

Accepted

time: 85ms

memory: 3636kb

input:

2 11 482884 164110
69 4

output:

result:

ok 1 number(s): "965768"

Test #27:

score: 0

Accepted

time: 3ms

memory: 3628kb

input:

2 14 49295 556296
29 97

output:

result:

ok 1 number(s): "98590"

Test #28:

score: 0

Accepted

time: 22ms

memory: 3636kb

input:

2 12 424218 948481
98 86

output:

result:

ok 1 number(s): "848436"

Test #29:

score: 0

Accepted

time: 1ms

memory: 3624kb

input:

2 17 73594 533496
33 77

output:

result:

ok 1 number(s): "147188"

Test #30:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

2 25 157018 49636
15 38

output:

result:

ok 1 number(s): "314036"

Test #31:

score: 0

Accepted

time: 86ms

memory: 3688kb

input:

2 11 273146 631185
92 92

output:

result:

ok 1 number(s): "273146"

Test #32:

score: -100

Wrong Answer

time: 0ms

memory: 3568kb

input:

2 34 23333 340667
58 79

output:

result:

wrong answer 1st numbers differ - expected: '46666', found: '23333'