oj.uz

답안 #1088107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1088107 2024-09-14T01:02:18 Z hahahaha Chorus (JOI23_chorus) C++17
40 / 100
 7000 ms 4404 KB 
#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

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.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 11 ms 1112 KB Output is correct
18 Correct 131 ms 1096 KB Output is correct
19 Correct 414 ms 2640 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 585 ms 4404 KB Output is correct
23 Correct 564 ms 4368 KB Output is correct
24 Correct 13 ms 348 KB Output is correct
25 Correct 580 ms 4224 KB Output is correct
26 Correct 450 ms 3668 KB Output is correct
27 Correct 182 ms 1616 KB Output is correct
28 Correct 175 ms 1616 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 11 ms 1112 KB Output is correct
18 Correct 131 ms 1096 KB Output is correct
19 Correct 414 ms 2640 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 585 ms 4404 KB Output is correct
23 Correct 564 ms 4368 KB Output is correct
24 Correct 13 ms 348 KB Output is correct
25 Correct 580 ms 4224 KB Output is correct
26 Correct 450 ms 3668 KB Output is correct
27 Correct 182 ms 1616 KB Output is correct
28 Correct 175 ms 1616 KB Output is correct
29 Execution timed out 7031 ms 1668 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 11 ms 1112 KB Output is correct
18 Correct 131 ms 1096 KB Output is correct
19 Correct 414 ms 2640 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 585 ms 4404 KB Output is correct
23 Correct 564 ms 4368 KB Output is correct
24 Correct 13 ms 348 KB Output is correct
25 Correct 580 ms 4224 KB Output is correct
26 Correct 450 ms 3668 KB Output is correct
27 Correct 182 ms 1616 KB Output is correct
28 Correct 175 ms 1616 KB Output is correct
29 Execution timed out 7031 ms 1668 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 508 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 11 ms 1112 KB Output is correct
18 Correct 131 ms 1096 KB Output is correct
19 Correct 414 ms 2640 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 585 ms 4404 KB Output is correct
23 Correct 564 ms 4368 KB Output is correct
24 Correct 13 ms 348 KB Output is correct
25 Correct 580 ms 4224 KB Output is correct
26 Correct 450 ms 3668 KB Output is correct
27 Correct 182 ms 1616 KB Output is correct
28 Correct 175 ms 1616 KB Output is correct
29 Execution timed out 7031 ms 1668 KB Time limit exceeded
30 Halted 0 ms 0 KB -