oj.uz

Submission #891940

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

const int 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] + 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;
    dp[mid][k]=inf;

    for(int i=mid;i>=1;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-1,optl,opt[mid][k],k);
    solve(mid+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=1;i<=n/2;i++){
        for(int f=1;f<=n;f++){
            sum[i][f]=max(i-pref[f],0)+sum[i-1][f-1];
            sum2[i][f]=max(i-pref[f],0)+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,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 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 4560 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 4560 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 4560 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 4560 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4696 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Incorrect 1 ms 4560 KB Output isn't correct
5 Halted 0 ms 0 KB -