| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 789333 |
2023-07-21T09:22:49 Z |
박상훈(#10042) |
Chorus (JOI23_chorus) |
C++17 |
|
2 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
char s[2002000];
int a[1001000], b[1001000], nxt[2002000], prv[2002000];
ll cst[505][505], dp_naive[505][505], sum[1001000];
inline ll cost(int l, int r){ // O(1)
int r2 = min(r, prv[a[r]]);
if (r2 < l) return 0;
return (ll)(r+1) * (r2-l+1) - (sum[r2] - sum[l-1]);
}
ll naive(int n, int k){
for (int i=1;i<=n;i++){
for (int j=i;j<=n;j++){
for (int k=i;k<=j;k++){
cst[i][j] += max(j-nxt[b[k]]+1, 0);
}
}
}
for (int i=0;i<=n;i++){
fill(dp_naive[i], dp_naive[i]+k+1, INF);
}
dp_naive[0][0] = 0;
for (int i=1;i<=n;i++){
for (int j=1;j<=k;j++){
for (int p=0;p<i;p++) dp_naive[i][j] = min(dp_naive[i][j], dp_naive[p][j-1] + cst[p+1][i]);
}
}
return dp_naive[n][k];
}
ll dp[1001000];
int dp2[1001000];
struct Hull{
vector<int> st, st2;
int pt, cap;
ll lambda;
void init(int n, ll _lambda){
st.clear();
st2.clear();
pt = 0;
cap = n;
lambda = _lambda;
}
inline ll calc(int f, int x){
assert(f < x);
return dp[f] + cost(f+1, x) * 2 + lambda;
}
int cross(int f, int g){
int l = g+1, r = cap, ret = cap+1;
while(l<=r){
int mid = (l+r)>>1;
if (calc(f, mid) > calc(g, mid)) ret = mid, r = mid-1;
else l = mid+1;
}
return ret;
}
void push(int x){
while(st.size() >= 2 && st2.back() >= x+1 && calc(st.back(), st2.back()) >= calc(x, st2.back())){
st.pop_back();
st2.pop_back();
}
if (st.size() >= 1 && calc(st.back(), cap) <= calc(x, cap)) return;
if (st.size() >= 1) st2.push_back(cross(st.back(), x));
st.push_back(x);
assert(st2.back() <= cap);
}
pair<ll, int> query(int x){
pt = min(pt, (int)st.size()-1);
while(pt+1<(int)st.size() && st2[pt] <= x) pt++;
return {calc(st[pt], x), dp2[st[pt]]+1};
}
}hull;
int alien(int n, ll lambda){ // y + \lambda x min
// monotone queue opt
hull.init(n, lambda);
hull.push(0);
for (int i=1;i<=n;i++){
auto [val, cnt] = hull.query(i);
dp[i] = val;
dp2[i] = cnt;
hull.push(i);
}
return dp2[n];
}
ll solve(int n, int k){
ll l = 0, r = 1e12 + 100, opt = -1;
while(l<=r){
ll mid = (l+r) / 2;
if (alien(n, mid*2-1) >= k) opt = mid, l = mid+1;
else r = mid-1;
}
assert(opt >= 0);
int cnt = alien(n, opt*2-1);
ll val = (dp[n] - (opt*2-1) * cnt) / 2;
if (cnt==k){
return val;
}
int cnt2 = alien(n, opt*2+1);
ll val2 = (dp[n] - (opt*2+1) * cnt2) / 2;
assert(cnt2 < k);
return val2 - opt * (k-cnt2);
}
int main(){
int n, k;
scanf("%d %d", &n, &k);
hull.st.reserve(n+100);
hull.st2.reserve(n+100);
scanf("%s", s+1);
int ptA = 1, ptB = 1;
for (int i=1;i<=n*2;i++){
if (s[i]=='A'){
// mp[i] = ptA;
prv[i] = ptB-1;
a[ptA++] = i;
}
else{
// mp[i] = ptB;
prv[i] = ptB;
b[ptB++] = i;
}
}
for (int i=n*2;i;i--){
if (s[i]=='A') nxt[i] = --ptA;
else nxt[i] = ptA;
}
for (int i=1;i<=n;i++) sum[i] = sum[i-1] + nxt[b[i]];
printf("%lld\n", solve(n, k));
}
Compilation message
chorus.cpp: In function 'int main()':
chorus.cpp:137:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | scanf("%d %d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:142:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
142 | scanf("%s", s+1);
| ~~~~~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
2 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
