QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#599151 | #6338. Chorus | Dimash | 0 | 0ms | 3556kb | C++23 | 1.8kb | 2024-09-29 01:51:59 | 2024-09-29 01:52:04 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e3 + 12, MOD = (int)1e9 + 7;
#define int ll
int n, k, x[N], y[N], pref[ 2 * N], col[N];
ll dp[N], c[N][N];
void prec() {
for(int i = 1; i <= n; i++) {
for(int j = i; j >= 1; j--) {
c[j][i] = c[j + 1][i];
if(y[j] <= x[i]) {
c[j][i] += pref[x[i]] - pref[y[j] - 1];;
}
}
}
}
pair<ll, ll> calc(ll pen) {
for(int i = 1; i <= n; i++) {
dp[i] = 1e18;
col[i] = n + 1;
for(int j = i; j >= 1; j--) {
if(make_pair(dp[j - 1] + c[j][i] - pen, col[j - 1] + 1) < make_pair(dp[i], col[i])) {
dp[i] = dp[j - 1] + c[j][i] - pen;
col[i] = col[j - 1] + 1;
}
}
}
return {dp[n], col[n]};
}
void test() {
cin >> n >> k;
int _x = 0, _y = 0;
for(int i = 1; i <= n + n; i++) {
char a;
cin >> a;
pref[i] = pref[i - 1];
if(a == 'A') {
x[++_x] = i;
pref[i]++;
} else {
y[++_y] = i;
}
}
prec();
// for(int i = -100; i <= 100; i++) {
// auto [val, t] = calc(i);
// cout << i << ' ' << val << ' ' << t << '\n';
// }
ll l = -1e12, r = 1e12, res;
while(r - l > 1) {
ll mid = (l + r) / 2;
auto [val, t] = calc(mid);
// cout << mid << ' ' << val << ' ' << t << '\n';
if(t >= k) {
r = mid;
res = val + k * 1ll * mid;
} else {
l = mid;
}
}
cout << res << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t = 1;
// cin >> t;
while(t--)
test();
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 16
Accepted
time: 0ms
memory: 3556kb
input:
1 1 BA
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Wrong Answer
time: 0ms
memory: 3544kb
input:
7 5 ABBAAABBABABBA
output:
2
result:
wrong answer 1st numbers differ - expected: '3', found: '2'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
0%