Submission #1213934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213934		Ak_16	Chorus (JOI23_chorus)	C++20	40 / 100	26 ms	4932 KiB

chorus

#include <iostream>
#include <string>
using namespace std;

int pos[100005];
int don[1005][1005];

int main() 
{
    int n,k;
    string s;
    cin>>n>>k;
    cin>>s;
    for(int i=1; i<=n; i++){
      for(int j=1; j<=n; j++){
        don[i][j] = 1e6;
      }
    }
    
    don[0][0] = 0;
    
    int cnt=0;
    for(int i=1; i<=2*n; i++){
      if(s[i-1]=='A'){
        cnt++;
        pos[cnt] = i;
      }
    }
    int sm = 0;
    for(int i=1; i<=n; i++){
      sm += pos[i];
      don[i][1] = sm - (i*(i+1))/2;
    }
    
    for(int i=2; i<=n; i++){
      for(int j=2; j<=i; j++){
        int cur=0;
        for(int k=1; k<=n+1-i; k++){
          cur += max(0, pos[i+k-1] - (2*i+k-2));
          don[i+k-1][j] = min(don[i+k-1][j], don[i-1][j-1] + cur);
        }
      }
    }

    cout<<don[n][k]<<endl;
}

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