QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#352203 | #8225. 最小值之和 | yaoxi_std | 0 | 2ms | 14080kb | C++14 | 3.4kb | 2024-03-12 23:27:47 | 2024-03-12 23:27:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
fprintf(stderr, "[%d] " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
constexpr int N = 55;
constexpr ll infll = 1e15;
int n;
ll a[N];
ll div_c(ll n, ll d) {
return n >= 0 ? (n + d - 1) / d : n / d;
}
struct dat {
ll val;
int pre;
bool operator<(const dat& rhs) const { return val < rhs.val; }
} dp[N][N][N][N];
bool Med;
int main() {
// debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
cin.tie(0)->sync_with_stdio(0);
cin >> n, --n;
for (int i = 0; i <= n; ++i) cin >> a[i];
for (int k = 1; k <= n; ++k) {
for (int l = 1, r = k; r <= n; ++l, ++r) {
ll vl = a[l - 1], vr = a[r];
if (k == 1) {
if (vl == vr) {
dp[l][r][k][0] = {-vl, l};
} else {
dp[l][r][k][0] = {1, -1};
}
} else {
for (int i = 0; i < k; ++i) dp[l][r][k][i] = {k + i, -1};
for (int p = l; p <= r; ++p) {
for (int i = 0; i < k; ++i) {
ll val = 0;
if (p == l) {
val = dp[p + 1][r][k][i].val;
if (val < -vl) val += k * div_c(-vl - val, k);
if (val != -vl) continue;
} else if (p == r) {
val = dp[l][p - 1][k][i].val;
if (val < -vr) val += k * div_c(-vr - val, k);
if (val != -vr) continue;
} else {
val = max(dp[l][p - 1][k][i].val, dp[p + 1][r][k][i].val);
}
chkmin(dp[l][r][k][i], dat{val, p});
}
}
}
for (int tk = k + 1; tk <= n; ++tk) {
for (int i = 0; i < tk; ++i) dp[l][r][tk][i] = {tk + i, -1};
for (int i = 0; i < k; ++i) {
int p = dp[l][r][k][i].val % tk;
if (p < 0) p += tk;
chkmin(dp[l][r][tk][p], dat{dp[l][r][k][i].val, i});
}
int gd = __gcd(k, tk);
for (int i = 0; i < gd; ++i) {
for (int j = 0, p = i; j < tk / gd * 2; ++j, p = (p + k) % tk) {
chkmin(dp[l][r][tk][(p + k) % tk], dat{dp[l][r][tk][p].val + k, dp[l][r][tk][p].pre});
}
}
}
}
}
if (dp[1][n][n][0].val > 0) return cout << "No\n", 0;
cout << "Yes\n";
function<void(int, int, int, int, ll, ll)> print =
[&](int l, int r, int k, int t, ll mn, ll cur) {
if (l > r) return;
int tk = r - l + 1;
if (k != tk) {
int p = dp[l][r][k][t].pre;
print(l, r, tk, p, mn + (dp[l][r][k][t].val - dp[l][r][tk][p].val) / tk, cur);
return;
}
if (l == r) {
cout << a[r] - cur << " \n"[l == n];
return;
}
int p = dp[l][r][k][t].pre;
mn = (-cur - dp[l][r][k][t].val) / k;
if (l < p) {
print(l, p - 1, k, t,
mn + (dp[l][r][k][t].val - dp[l][p - 1][k][t].val) / k,
cur + (r - p + 1) * mn);
}
cout << mn << " \n"[p == n];
if (p < r) {
print(p + 1, r, k, t,
mn + (dp[l][r][k][t].val - dp[p + 1][r][k][t].val) / k,
cur + (p - l + 1) * mn);
}
};
print(1, n, n, 0, 0, 0);
return 0;
}
/*
g++ -std=c++14 -O2 -o QOJ8225 QOJ8225.cpp
-Wall -Wextra -Wshadow
-fsanitize=address,undefined -g
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 2ms
memory: 11744kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: 0
Accepted
time: 0ms
memory: 11800kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: 0
Accepted
time: 2ms
memory: 12024kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 0
Accepted
time: 0ms
memory: 12020kb
input:
5 11 11 10 5 5
output:
Yes 5 4 1 2
result:
ok The answer is correct.
Test #5:
score: 0
Accepted
time: 2ms
memory: 13860kb
input:
5 10 10 10 4 4
output:
Yes 4 4 1 1
result:
ok The answer is correct.
Test #6:
score: 0
Accepted
time: 0ms
memory: 11692kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 0
Accepted
time: 2ms
memory: 11808kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 0
Accepted
time: 0ms
memory: 11696kb
input:
5 2 2 6 11 11
output:
Yes 2 0 3 8
result:
ok The answer is correct.
Test #9:
score: 0
Accepted
time: 2ms
memory: 14080kb
input:
5 10 10 8 5 5
output:
Yes 5 3 1 2
result:
ok The answer is correct.
Test #10:
score: 0
Accepted
time: 0ms
memory: 13852kb
input:
5 24 24 28 28 26
output:
Yes 6 6 9 7
result:
ok The answer is correct.
Test #11:
score: 0
Accepted
time: 2ms
memory: 11968kb
input:
5 5 5 22 31 31
output:
Yes 2 1 10 19
result:
ok The answer is correct.
Test #12:
score: 0
Accepted
time: 2ms
memory: 13856kb
input:
5 8 33 38 38 29
output:
Yes 2 11 16 9
result:
ok The answer is correct.
Test #13:
score: 0
Accepted
time: 0ms
memory: 11732kb
input:
5 16 16 4 12 12
output:
Yes 13 1 1 9
result:
ok The answer is correct.
Test #14:
score: 0
Accepted
time: 2ms
memory: 11768kb
input:
5 29 29 24 26 26
output:
Yes 11 6 6 8
result:
ok The answer is correct.
Test #15:
score: 0
Accepted
time: 0ms
memory: 11692kb
input:
5 0 33 33 32 32
output:
Yes 0 13 10 12
result:
ok The answer is correct.
Test #16:
score: 0
Accepted
time: 2ms
memory: 11776kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 0ms
memory: 11764kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 0ms
memory: 11804kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 0ms
memory: 11808kb
input:
5 0 1 0 4 2
output:
No
result:
ok The answer is correct.
Test #20:
score: 0
Accepted
time: 1ms
memory: 11752kb
input:
5 12 21 21 13 4
output:
No
result:
ok The answer is correct.
Test #21:
score: 0
Accepted
time: 1ms
memory: 11804kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 0ms
memory: 11788kb
input:
5 6 7 7 6 6
output:
Yes 2 3 1 3
result:
ok The answer is correct.
Test #23:
score: 0
Accepted
time: 1ms
memory: 11792kb
input:
5 25 25 24 20 20
output:
Yes 8 7 5 5
result:
ok The answer is correct.
Test #24:
score: 0
Accepted
time: 1ms
memory: 12020kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 0ms
memory: 11740kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 1ms
memory: 11788kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 0ms
memory: 11792kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 2ms
memory: 11812kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 2ms
memory: 11744kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 2ms
memory: 14028kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 1ms
memory: 5836kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 0ms
memory: 3776kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: -11
Wrong Answer
time: 1ms
memory: 3640kb
input:
1 233
output:
Yes
result:
wrong answer Line 1 expected
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%