QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#762615 | #8225. 最小值之和 | rizynvu | 0 | 2ms | 10444kb | C++14 | 3.4kb | 2024-11-19 15:49:14 | 2024-11-19 15:49:19 |
Judging History
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], mn[maxn][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 len = r - l, z = x % len;
ll y = f[l][r][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]), mn[i][i] = a[i];
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
mn[i][j] = std::min(mn[i][j - 1], a[j]);
}
}
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++) {
ll d = h[i] - mn[l][r];
if (d > 0) {
ll c = (d + z - 1) / z;
h[i] -= c * z;
}
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
Wrong Answer
Test #1:
score: 11
Accepted
time: 2ms
memory: 10304kb
input:
5 14 14 12 13 13
output:
Yes 5 3 3 4
result:
ok The answer is correct.
Test #2:
score: 11
Accepted
time: 1ms
memory: 8764kb
input:
5 4 4 7 7 4
output:
Yes 1 1 4 1
result:
ok The answer is correct.
Test #3:
score: 11
Accepted
time: 1ms
memory: 10360kb
input:
5 4 13 14 14 13
output:
Yes 1 4 5 4
result:
ok The answer is correct.
Test #4:
score: 11
Accepted
time: 1ms
memory: 10444kb
input:
5 11 11 10 5 5
output:
Yes 5 4 1 2
result:
ok The answer is correct.
Test #5:
score: 11
Accepted
time: 0ms
memory: 10212kb
input:
5 10 10 10 4 4
output:
Yes 4 4 1 1
result:
ok The answer is correct.
Test #6:
score: 11
Accepted
time: 1ms
memory: 9452kb
input:
5 20 20 17 7 4
output:
Yes 10 7 2 1
result:
ok The answer is correct.
Test #7:
score: 11
Accepted
time: 1ms
memory: 9508kb
input:
5 12 12 16 19 19
output:
Yes 3 3 5 8
result:
ok The answer is correct.
Test #8:
score: 0
Wrong Answer
time: 0ms
memory: 10012kb
input:
5 2 2 6 11 11
output:
Yes 0 0 2 7
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%