QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352204 | #8225. 最小值之和 | yaoxi_std | 26 | 25ms | 51092kb | C++14 | 3.5kb | 2024-03-12 23:28:20 | 2024-03-12 23:28:21 |
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];
if (!n) return cout << (!a[0] ? "Yes" : "No") << '\n', 0;
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
*/
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 11
Accepted
Test #1:
score: 11
Accepted
time: 1ms
memory: 11736kb
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: 2ms
memory: 11692kb
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: 1ms
memory: 11792kb
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: 11960kb
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: 0ms
memory: 11784kb
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: 1ms
memory: 11800kb
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: 1ms
memory: 11684kb
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: 1ms
memory: 12000kb
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: 1ms
memory: 11732kb
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: 1ms
memory: 11996kb
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: 1ms
memory: 13852kb
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: 1ms
memory: 11800kb
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: 1ms
memory: 11784kb
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: 1ms
memory: 11792kb
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: 1ms
memory: 12016kb
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: 1ms
memory: 11740kb
input:
5 20 16 8 25 22
output:
No
result:
ok The answer is correct.
Test #17:
score: 0
Accepted
time: 1ms
memory: 11768kb
input:
5 0 2 3 0 2
output:
No
result:
ok The answer is correct.
Test #18:
score: 0
Accepted
time: 1ms
memory: 11768kb
input:
5 28 23 29 29 24
output:
No
result:
ok The answer is correct.
Test #19:
score: 0
Accepted
time: 1ms
memory: 11740kb
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: 11828kb
input:
5 9 22 25 23 12
output:
No
result:
ok The answer is correct.
Test #22:
score: 0
Accepted
time: 1ms
memory: 11732kb
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: 11796kb
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: 14076kb
input:
5 17 9 8 16 9
output:
No
result:
ok The answer is correct.
Test #25:
score: 0
Accepted
time: 1ms
memory: 11716kb
input:
5 20 5 34 34 23
output:
No
result:
ok The answer is correct.
Test #26:
score: 0
Accepted
time: 1ms
memory: 11764kb
input:
5 15 33 35 35 31
output:
No
result:
ok The answer is correct.
Test #27:
score: 0
Accepted
time: 1ms
memory: 11744kb
input:
5 21 22 23 1 18
output:
No
result:
ok The answer is correct.
Test #28:
score: 0
Accepted
time: 0ms
memory: 11832kb
input:
5 4 2 3 4 2
output:
No
result:
ok The answer is correct.
Test #29:
score: 0
Accepted
time: 0ms
memory: 14064kb
input:
5 16 25 8 19 7
output:
No
result:
ok The answer is correct.
Test #30:
score: 0
Accepted
time: 1ms
memory: 11740kb
input:
5 4 0 8 6 6
output:
No
result:
ok The answer is correct.
Test #31:
score: 0
Accepted
time: 1ms
memory: 5588kb
input:
2 2 3
output:
No
result:
ok The answer is correct.
Test #32:
score: 0
Accepted
time: 0ms
memory: 5664kb
input:
2 2 2
output:
Yes 2
result:
ok The answer is correct.
Test #33:
score: 0
Accepted
time: 1ms
memory: 3596kb
input:
1 0
output:
Yes
result:
ok The answer is correct.
Test #34:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
1 233
output:
No
result:
ok The answer is correct.
Subtask #2:
score: 15
Accepted
Dependency #1:
100%
Accepted
Test #35:
score: 15
Accepted
time: 0ms
memory: 17940kb
input:
8 16 16 8 8 9 9 6 6
output:
Yes 16 0 4 1 5 1 2
result:
ok The answer is correct.
Test #36:
score: 0
Accepted
time: 0ms
memory: 17904kb
input:
8 16 16 9 21 21 23 23 23
output:
Yes 10 1 2 14 1 9 9
result:
ok The answer is correct.
Test #37:
score: 0
Accepted
time: 2ms
memory: 17868kb
input:
8 10 10 15 15 15 10 10 5
output:
Yes 10 0 6 6 1 6 1
result:
ok The answer is correct.
Test #38:
score: 0
Accepted
time: 2ms
memory: 20220kb
input:
8 13 13 15 15 24 24 24 10
output:
Yes 7 1 9 1 9 9 2
result:
ok The answer is correct.
Test #39:
score: 0
Accepted
time: 0ms
memory: 18164kb
input:
8 5 13 16 25 25 24 4 4
output:
Yes 1 3 4 9 8 0 4
result:
ok The answer is correct.
Test #40:
score: 0
Accepted
time: 0ms
memory: 17880kb
input:
8 1313 1695 1695 1129 1129 711 557 557
output:
Yes 459 841 79 575 157 80 80
result:
ok The answer is correct.
Test #41:
score: 0
Accepted
time: 3ms
memory: 17892kb
input:
8 1386 1416 1416 1069 1069 390 645 645
output:
Yes 554 584 56 735 56 55 315
result:
ok The answer is correct.
Test #42:
score: 0
Accepted
time: 0ms
memory: 19932kb
input:
8 3377 3377 3164 3164 3570 3570 3365 3365
output:
Yes 665 452 452 452 726 518 521
result:
ok The answer is correct.
Test #43:
score: 0
Accepted
time: 2ms
memory: 18176kb
input:
8 28167709 33181201 33829300 33829300 21924091 26145199 28398185 28398185
output:
Yes 5213219 7719965 8368064 3132013 3132013 5242567 7495553
result:
ok The answer is correct.
Test #44:
score: 0
Accepted
time: 0ms
memory: 20096kb
input:
8 4726918 12793592 12793592 6681214 13995142 22020836 22566624 22566624
output:
Yes 675274 7113378 1000988 1000991 3438967 7451814 7997602
result:
ok The answer is correct.
Test #45:
score: 0
Accepted
time: 2ms
memory: 17904kb
input:
8 9146297 15736298 15736298 16471005 16471005 14187656 14187656 6001415
output:
Yes 2429786 9019787 857345 11326935 857345 9043586 857345
result:
ok The answer is correct.
Test #46:
score: 0
Accepted
time: 1ms
memory: 18164kb
input:
8 25115296 25115296 22120670 21035156 20603135 28703897 28703897 27553199
output:
Yes 6624695 3630069 3087312 2943305 2943305 7569035 6418337
result:
ok The answer is correct.
Test #47:
score: 0
Accepted
time: 0ms
memory: 19956kb
input:
8 22440147 22440147 22626721 22626721 22592252 22592252 19174074 19174074
output:
Yes 6005229 2739153 6191803 2739153 6157332 2739154 2739154
result:
ok The answer is correct.
Test #48:
score: 0
Accepted
time: 2ms
memory: 17956kb
input:
8 12 0 13 8 18 18 18 0
output:
No
result:
ok The answer is correct.
Test #49:
score: 0
Accepted
time: 2ms
memory: 17904kb
input:
8 3 23 13 18 26 12 25 25
output:
No
result:
ok The answer is correct.
Test #50:
score: 0
Accepted
time: 2ms
memory: 17940kb
input:
8 1353255 1004808 981534 1400692 1246708 409750 1177255 1177255
output:
No
result:
ok The answer is correct.
Test #51:
score: 0
Accepted
time: 0ms
memory: 20224kb
input:
8 96 96 99 99 4 94 39 36
output:
No
result:
ok The answer is correct.
Test #52:
score: 0
Accepted
time: 0ms
memory: 17812kb
input:
8 15 21 0 20 20 15 13 6
output:
No
result:
ok The answer is correct.
Test #53:
score: 0
Accepted
time: 2ms
memory: 19928kb
input:
8 2 1 0 2 6 6 5 1
output:
No
result:
ok The answer is correct.
Test #54:
score: 0
Accepted
time: 2ms
memory: 19884kb
input:
8 7 12 11 11 1 11 4 11
output:
No
result:
ok The answer is correct.
Test #55:
score: 0
Accepted
time: 2ms
memory: 18168kb
input:
8 18 3 27 27 19 10 6 6
output:
No
result:
ok The answer is correct.
Subtask #3:
score: 0
Wrong Answer
Dependency #2:
100%
Accepted
Test #56:
score: 0
Wrong Answer
time: 0ms
memory: 22188kb
input:
14 10 10 2 30 45 50 50 47 47 47 46 33 33 32
output:
Yes 9 1 0 4 9 14 11 2 15 13 3 8 6
result:
wrong answer Your answer is wrong.
Subtask #4:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #77:
score: 25
Accepted
time: 25ms
memory: 40672kb
input:
49 28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4
output:
Yes 14 14 0 12 25 0 9 12 5 7 21 0 41 0 5 12 15 10 3 17 18 0 9 0 7 10 1 0 17 0 3 5 9 0 13 0 0 6 0 4 6 10 5 0 2 9 7 1
result:
ok The answer is correct.
Test #78:
score: -25
Wrong Answer
time: 20ms
memory: 51092kb
input:
49 3 3 29 29 31 31 34 34 34 34 31 22 22 21 21 21 36 36 37 42 42 41 22 22 6 6 19 37 65 71 71 77 78 78 76 76 42 46 46 40 60 60 60 60 60 60 6 6 4
output:
Yes 3 0 29 0 31 0 34 0 14 11 3 7 6 0 21 0 36 0 9 13 12 4 6 0 6 0 4 10 24 30 1 36 37 0 76 0 21 25 0 20 40 0 60 0 57 1 3 1
result:
wrong answer Your answer is wrong.
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%