Submission #891960

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
891960	2023-12-24T13:57:32 Z	alexander707070	Chorus (JOI23_chorus)	C++14	Compilation error	0 ms	0 KB

chorus

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

const long long inf=1e15;

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

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

long long 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;
}

Compilation message

/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status