제출 #891963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
891963		alexander707070	Chorus (JOI23_chorus)	C++14	61 / 100	3945 ms	650908 KiB

chorus

#include<bits/stdc++.h>
#define MAXN 10007
using namespace std;

const int inf=1e9;

int n,k;
int ans;
char s[MAXN];

int dp[MAXN][MAXN];
int opt[MAXN][MAXN],pref[MAXN];
int sum[MAXN][MAXN],sum2[MAXN][MAXN];

int cost(int l,int r){
    if((r-l+1)%2!=0)return inf;

    return (sum[(r-l+1)/2][(l+r)/2] - sum[0][(l+r)/2-(r-l+1)/2] + sum2[(r-l+1)/2-1][(l+r)/2+1])/2;    
}

void solve(int l,int r,int optl,int optr,int k){
    if(l>r)return;

    int mid=((l+r)/2)*2;

    dp[mid][k]=inf;
    opt[mid][k]=optr;

    for(int i=min(mid,optr);i>=optl;i--){
        if(dp[i-1][k-1]+cost(i,mid)<dp[mid][k]){
            dp[mid][k]=dp[i-1][k-1]+cost(i,mid);
            opt[mid][k]=i;
        }
    }

    solve(l,mid/2-1,optl,opt[mid][k],k);
    solve(mid/2+1,r,opt[mid][k],optr,k);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>k; 
    n*=2;
    cin>>(s+1);

    for(int i=1;i<=n;i++){
        if(s[i]=='A')pref[i]++;
        else pref[i]--;
        pref[i]+=pref[i-1];
    }

    for(int i=0;i<=n/2;i++){
        for(int f=1;f<=n;f++){
            sum[i][f]=max(i-pref[f],0);
            if(i>0)sum[i][f]+=sum[i-1][f-1];

            sum2[i][f]=max(i-pref[f],0);
            if(i>0)sum2[i][f]+=sum2[i-1][f+1];
        }
    }

    for(int i=1;i<=n;i++){
        dp[i][0]=inf;
    }

    ans=inf;
    for(int i=1;i<=k;i++){
        solve(1,n/2,1,n,i);
        ans=min(ans,dp[n][i]);
    }

    cout<<ans<<"\n";

    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 21 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13