QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#324970 | #6372. Dance | HaccerKat | RE | 8ms | 12012kb | C++20 | 3.4kb | 2024-02-11 02:28:00 | 2024-02-11 02:28:01 |
Judging History
answer
#include "bits/stdc++.h"
#ifdef DEBUG
#include "algo/debug.hpp"
#else
#define dbg(...)
#define dbgm(...)
#endif
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
// using u128 = __uint128_t;
// using i128 = __int128;
const int mod = 1000000007;
const int N = 205;
const int D = 1 << 10;
const int LOG = 20;
const int inf = 1e9;
const double eps = 1e-11;
int p[N], f[D * D], nf[D * D], g[D][D], ng[D][D];
int n, m, qq, d, a, b, mx = 0;
void solve1() {
int k = 1 << d, l = k / 2;
fill(f, f + D * D, inf);
f[0] = 0;
for (int i = 0; i < mx; i++) {
swap(f, nf);
fill(f, f + D * D, inf);
for (int mask = 0; mask < k; mask++) {
bool move = 0;
if (i >= d) {
if (!(mask & 1) && p[i - d]) move = 1;
}
int x = (mask >> d - 1) ? b : a;
int msk = mask >> 1;
if (!move) f[msk] = min(f[msk], nf[mask]);
f[msk | l] = min(f[msk | l], nf[mask] + x);
}
}
int out = inf;
for (int mask = 0; mask < k; mask++) {
out = min(out, f[mask]);
}
cout << out << "\n";
}
void solve2() {
int s = (mx + d - 1) / d, k = 1 << s;
// dbgm(s, k, mx);
for (int i = 0; i < D; i++) {
fill(g[i], g[i] + D, inf);
}
g[0][0] = 0;
for (int i = 0; i < d; i++) {
for (int j = 0; j * d + i < mx; j++) {
swap(g, ng);
for (int x = 0; x < D; x++) {
fill(g[x], g[x] + D, inf);
}
int pos = j * d + i;
for (int mask = 0; mask < k; mask++) {
for (int smask = 0; smask < k; smask++) {
bool move = 0;
if (j) {
if (!((mask >> j - 1) & 1) && p[pos - d]) move = 1;
}
int bit = (mask >> j) & 1, x = bit ? b : a;
if (i == d - 1 && pos < mx - 1 && ((smask >> j + 1) & 1)) {
x += b - a;
}
// dbgm(i, j, mask, smask, move, x, pos, ng[mask][smask]);
int bv = (1 << j), v = bv * bit, msk = mask ^ v;
int smsk = i == 0 ? msk : smask;
if (!move) {
g[msk][smsk] = min(g[msk][smsk], ng[mask][smask]);
}
msk ^= bv;
if (i == 0) smsk ^= bv;
g[msk][smsk] = min(g[msk][smsk], ng[mask][smask] + x);
}
}
// dbgm(i, j, x);
// dbg(g);
}
}
int out = inf;
for (int mask = 0; mask < k; mask++) {
for (int smask = 0; smask < k; smask++) {
out = min(out, g[mask][smask]);
}
}
cout << out << "\n";
}
void solve() {
cin >> n >> d >> a >> b;
b = min(a, b);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
mx = max(mx, x);
x--;
p[x] = 1;
}
d *= 2, mx += d;
if (d <= 0) solve1();
else solve2();
}
int32_t main() {
std::ios::sync_with_stdio(false);
cin.tie(NULL);
solve();
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 12012kb
input:
3 1 2 1 4 1 7
output:
5
result:
ok 1 number(s): "5"
Test #2:
score: 0
Accepted
time: 8ms
memory: 11784kb
input:
3 1 7 1 4 1 7
output:
11
result:
ok 1 number(s): "11"
Test #3:
score: 0
Accepted
time: 6ms
memory: 11784kb
input:
1 1 441060 865580 6
output:
441060
result:
ok 1 number(s): "441060"
Test #4:
score: -100
Runtime Error
input:
1 2 524484 157528 88