QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#352091 | #8225. 最小值之和 | yaoxi_std | 0 | 1ms | 3832kb | C++14 | 3.2kb | 2024-03-12 20:43:09 | 2024-03-12 20:43:10 |
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)> print =
[&](int l, int r, int k, int t, ll mn) {
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);
return;
}
if (l == r) {
cout << mn << " \n"[l == n];
return;
}
int p = dp[l][r][k][t].pre;
print(l, p - 1, k, t, mn + (dp[l][r][k][t].val - dp[l][p - 1][k][t].val) / k);
cout << mn << " \n"[p == n];
print(p + 1, r, k, t, mn + (dp[l][r][k][t].val - dp[p + 1][r][k][t].val) / k);
};
print(1, n, n, 0, -dp[1][n][n][0].val / n);
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: 0
Wrong Answer
Test #1:
score: 11
Accepted
time: 1ms
memory: 3616kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: -11
Wrong Answer
time: 0ms
memory: 3832kb
input:
5 4 4 7 7 4
output:
Yes 1 1 3 1
result:
wrong answer Your answer is wrong.
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%