QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762567 | #8225. 最小值之和 | rizynvu | 0 | 0ms | 0kb | C++14 | 3.1kb | 2024-11-19 15:32:55 | 2024-11-19 15:33:10 |
answer
#include<bits/stdc++.h>
using ll = long long;
inline void fmax(ll &x, ll y) {
x < y && (x = y);
}
inline void fmax(ll &x, ll y, int &xp, int yp) {
x < y && (x = y, xp = yp);
}
inline int exgcd(int a, int b, ll &x, ll &y) {
if (! b) {
x = 1, y = 0;
return a;
}
int g = exgcd(b, a % b, y, x);
y -= 1ll * a / b * x;
return g;
}
constexpr int maxn = 80 + 5;
int n;
ll a[maxn], b[maxn];
ll f[maxn][maxn][maxn], h[maxn];
int fp[maxn][maxn][maxn];
void dfs(int l, int r, ll x) {
if (l == r) return ;
int z = x % (r - l);
ll y = f[l][r][z];
for (int i = l; i <= r; i++) {
y = std::min(y, (ll)a[i] / z * z);
}
assert(y >= x);
for (int i = l; i < r; i++) {
b[i] += (y - x) / (r - l);
}
dfs(l, fp[l][r][z], y), dfs(fp[l][r][z] + 1, r, y);
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
if (n == 1) {
puts(a[1] == 0 ? "Yes" : "No");
return 0;
}
memset(f, -1, sizeof(f));
for (int len = 1; len < n; len++) {
for (int l = 1, r = len + 1; r <= n; l++, r++) {
for (int p = l; p < r; p++) {
int L = p - l, R = r - (p + 1);
if (! L && ! R) {
if (a[l] == a[r]) {
fmax(f[l][r][0], a[l], fp[l][r][0], p);
}
} else if (! L) {
if (f[p + 1][r][a[l] % R] >= a[l]) {
fmax(f[l][r][a[l] % len], a[l], fp[l][r][a[l] % len], p);
}
} else if (! R) {
if (f[l][p][a[r] % L] >= a[r]) {
fmax(f[l][r][a[r] % len], a[r], fp[l][r][a[r] % len], p);
}
} else {
ll x, y; int g = exgcd(L, R, x, y);
y = -y;
assert(x * L + y * -R == g);
int z = L * R / g;
memset(h, -1, sizeof(ll) * len);
for (int a = 0; a < L; a++) {
for (int b = 0; b < R; b++) {
ll fl = f[l][p][a], fr = f[p + 1][r][b];
if (fl == -1 || fr == -1) continue;
if ((fl - fr) % g) continue;
ll val = (fl - fr) / g;
ll fx = x * val, fy = y * val;
fy = (fy % z + z) % z;
ll F = fr - fy * R;
if (F < 0) continue;
fmax(h[F % len], F);
}
}
for (int i = 0, ed = std::__gcd(z, len); i < ed; i++) {
for (int j = i, c = 0; c < 2; (j += len - z % len) %= len, c += j == i) {
fmax(h[(j + len - z % len) % len], h[j] - z);
}
}
for (int i = 0; i < len; i++) {
fmax(f[l][r][i], h[i], fp[l][r][i], p);
}
}
}
}
}
if (f[1][n][0] == -1) {
return puts("No"), 0;
}
puts("Yes");
dfs(1, n, 0);
for (int i = 1; i < n; i++) {
printf("%lld ", b[i]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Runtime Error
Test #1:
score: 0
Runtime Error
input:
5 14 14 12 13 13
output:
result:
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%