Submission #741746

#	Time	Username	Problem	Language	Result	Execution time	Memory
741746		Username4132	Chorus (JOI23_chorus)	C++14	40 / 100	7048 ms	81396 KiB

chorus

#include<iostream>
#include<vector>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define dforn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back

const int MAXN=5010, INF=1e7;
int n, K, pos[MAXN], cost[MAXN][MAXN], dp[MAXN][MAXN];
char str[MAXN];
vector<bool> imp;

int main(){
    scanf("%d %d", &n, &K);
    scanf("%s", str);
    forn(i, n){
        int cnA=0, cnB=0, cn=0;
        forn(j, 2*n){
            if(str[j]=='A'){
                cnA++;
                if(cnA>i) imp.PB(0);
            }
            else{
                cnB++;
                if(cnB>i) imp.PB(1);
            }
        }
        forn(j, 2*(n-i)) if(!imp[j]) pos[cn++]=j;
        forsn(j, 1, cn+1) cost[i][j]=cost[i][j-1]+pos[j-1]-j+1;
        imp.clear();
    }
    forn(i, n) dp[0][i]=INF;
    forsn(i, 1, K+1) dp[i][n]=INF;
    forsn(i, 1, K+1) dforn(j, n){
        dp[i][j]=INF;
        forsn(k, 1, n-j+1) dp[i][j]=min(dp[i][j], dp[i-1][j+k] + cost[j][k]);
    }
    printf("%d\n", dp[K][0]);
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d %d", &n, &K);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf("%s", str);
      |     ~~~~~^~~~~~~~~~~

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