QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#405835 | #8225. 最小值之和 | chenk | 0 | 2ms | 9836kb | C++14 | 3.1kb | 2024-05-06 14:30:14 | 2024-05-06 14:30:14 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define rep(i, s, t) for (int i = s; i <= t; ++i)
#define per(i, s, t) for (int i = t; i >= s; --i)
const int N = 85;
int n, a[N];
int f[N][N][N];
tuple<int, int, int, int, int> las[N][N][N];
int g[N][N], sx[N][N], sy[N][N];
int ans[N];
int exgcd(int a, int b, int& x, int& y) {
if(b == 0) {
x = 1, y = 0;
return a;
}
int tx, ty;
int g = exgcd(b, a%b, tx, ty);
x = ty;
y = tx - (a / b) * ty;
return g;
}
inline void dfs(int l, int r, int i) {
//cerr << l << " " << r << " " << i << "\n";
if(l >= r) return;
auto [k, a, b, x, y] = las[l][r][i];
rep(j, l, k-1) ans[j] += x;
rep(j, k+1, r-1) ans[j] += y;
dfs(l, k, a);
dfs(k+1, r, b);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(15);
cin >> n;
rep(i, 1, n) cin >> a[i];
if(n == 1) {
cout << (a[1] ? "No" : "Yes") << "\n";
return 0;
}
rep(i, 1, n) rep(j, 1, n) g[i][j] = exgcd(i, j, sx[i][j], sy[i][j]);
memset(f, -1, sizeof f);
rep(i, 1, n) f[i][i][0] = a[i];
rep(len, 2, n) rep(i, 1, n) {
int j = i + len - 1;
if(j > n) break;
rep(k, i, j-1) rep(a, 0, k-i) if(f[i][k][a] != -1) rep(b, 0, j-k-1) if(f[k+1][j][b] != -1) {
//cerr << "[" << i << ", " << k << ", " << a << "](" << f[i][k][a] << ") + [" << k+1 << ", " << j << ", " << b << "](" << f[k+1][j][b] << ")\n";
int lenA = k-i, lenB = j-k-1;
int p = f[i][k][a], q = f[k+1][j][b];
ll x = -1, y = -1;
int g = ::g[lenA][lenB];
if(lenA == 0 && lenB == 0) {
if(p == q) {
x = y = 0;
} else {
continue;
}
} else if(lenA == 0) {
if(q >= p && (q - p) % lenB == 0) {
x = 0, y = (q - p) / lenB;
} else {
continue;
}
} else if(lenB == 0) {
if(p >= q && (p - q) % lenA == 0) {
x = (p - q) / lenA, y = 0;
} else {
continue;
}
} else {
if((p - q) % g) continue;
x = sx[lenA][lenB];
y = sy[lenA][lenB];
x *= (p - q) / g;
y *= -(p - q) / g;
x %= lenB / g; if(x < 0) x += lenB / g;
y = (q - p + x * lenA) / lenB;
if(y < 0) {
y %= lenA / g; if(y < 0) y += lenA / g;
x = (p - q + y * lenB) / lenA;
if(x < 0) continue;
}
}
assert(p - x * lenA == q - y * lenB);
int t = g ? lenA * lenB / g : 0;
int dx = g ? lenB / g : 0;
int dy = g ? lenA / g : 0;
int val = p - x * lenA;
if(val < 0) continue;
int len = j - i;
rep(p, 1, len) {
if(val < 0) break;
if(val > f[i][j][val % len]) {
f[i][j][val % len] = val;
las[i][j][val % len] = {k, a, b, x, y};
}
val -= t;
x += dx;
y += dy;
}
}
}
if(f[1][n][0] > 0) {
cout << "Yes" << "\n";
dfs(1, n, 0);
rep(i, 1, n-1) ans[i] += f[1][n][0] / (n-1);
rep(i, 1, n-1) cout << ans[i] << " \n"[i == n-1];
} else {
cout << "No" << "\n";
}
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: 9748kb
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: 0ms
memory: 9688kb
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: 6364kb
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: 6228kb
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: 9836kb
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: 6736kb
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: 6324kb
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: 1ms
memory: 6020kb
input:
5 2 2 6 11 11
output:
No
result:
wrong answer Line 1 expected , found Ga
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%