oj.uz

Submission #891962

# Submission time Handle Problem Language Result Execution time Memory
891962 2023-12-24T13:58:09 Z alexander707070 Chorus (JOI23_chorus) C++14
0 / 100
 1 ms 12632 KB 
#include<bits/stdc++.h>
#define MAXN 10007
using namespace std;

const int inf=1e15;

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

Compilation message

chorus.cpp:5:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
    5 | const int inf=1e15;
      |               ^~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -