Submission #1088107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088107		hahahaha	Chorus (JOI23_chorus)	C++17	40 / 100	7031 ms	4404 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
char s[2000009];
typedef long long ll;
ll a[1000009], psum[1000009], dp[3009][3009];
ll cost(int k, int j){
    int idx = lower_bound(a+k, a+j, k-1) - a;
    //printf("k=%d j=%d idx=%d ret=%d\n", k, j, idx, psum[j-1] - psum[idx-1] - (k-1) * (j-idx));
    return psum[j-1] - psum[idx-1] - (k-1) * (j-idx);
}
int main(){
    int n, k, i, j, j2, cur = 0, cnt = 0;
    scanf("%d %d", &n, &k);
    scanf(" %s", s);
    for(i=0; i<2*n; i++){
        if(s[i] == 'A'){
            a[++cnt] = cur;
            //printf("a[%d]=%d\n", cnt, cur);
        }
        else
            cur++;
    }
    for(i=1; i<=n; i++)psum[i] = psum[i-1] + a[i];
    for(j=1; j<=n+1; j++)
        dp[1][j] = cost(1, j);
    for(i=2; i<=k; i++){
        for(j=1; j<=n+1; j++){
            dp[i][j] = 1000000000;
            for(j2=1; j2<j; j2++)
                dp[i][j]= min(dp[i][j], dp[i-1][j2] + cost(j2, j));
        }
    }
    printf("%d\n", dp[k][n+1]);
    return 0;
}

Compilation message (stderr)

chorus.cpp: In function 'int main()':
chorus.cpp:33:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll' {aka 'long long int'} [-Wformat=]
   33 |     printf("%d\n", dp[k][n+1]);
      |             ~^     ~~~~~~~~~~
      |              |              |
      |              int            ll {aka long long int}
      |             %lld
chorus.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~

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