oj.uz

Submission #1037917

# Submission time Handle Problem Language Result Execution time Memory
1037917 2024-07-29T10:04:16 Z 김은성(#10980) Chorus (JOI23_chorus) C++17
0 / 100
 1 ms 8540 KB 
#include <bits/stdc++.h>
using namespace std;
char s[2000009];
typedef long long ll;
const ll INF = 0x3ffffffffffffff;
ll a[1000009], psum[1000009], dp[3009][3009];
pair<int, int> tree[1<<21]; //(i, j) -> dp[i][j] + cost(j, *)
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] - (ll)(k-1) * (j-idx);
}
ll evaluate(pair<int, int> idx, int x){
    if(idx.first == -1)
        return INF;
    if(idx.second >= x)
        return INF;
    return dp[idx.first][idx.second] + cost(idx.second, x);
}
void update(int v, int l, int r, pair<int, int> idx){
    int mid = (l+r)/2;
    if(evaluate(tree[v], mid) > evaluate(idx, mid))
        swap(idx, tree[v]);
    if(evaluate(idx, l) < evaluate(tree[v], l))
        update(2*v,l , mid, idx);
    else if(l != r)
        update(2*v+1, mid+1, r, idx);
}
ll query(int v, int l, int r, int x){
    ll ans = evaluate(tree[v], x);
   // printf("ans=%lld\n", ans);
    int mid = (l+r)/2;
    if(l==r)
        return ans;
    if(x <= mid)
        ans = min(ans, query(2*v, l, mid, x));
    if(x > mid)
        ans = min(ans, query(2*v+1, mid+1, r, x));
    return ans;
}
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(i=1; i<=5*n; i++)
        tree[i] = make_pair(-1, -1);
    for(j=1; j<=n+1; j++){
        dp[1][j] = cost(1, j);
        update(1, 1, n+1, make_pair(1, j));
    }
    for(i=2; i<=k; i++){
        for(j=1; j<=n+1; j++){
            dp[i][j]= min(INF, query(1, 1, n+1, j));
            //printf("dp[%d][%d]=%lld\n", i, j, dp[i][j]);
        }
        for(j=1; j<=5*n; j++)
            tree[j] = make_pair(-1, -1);
        for(j=1; j<=n+1; j++){
            update(1, 1, n+1, make_pair(i, j));
        }
    }
    printf("%lld\n", dp[k][n+1]);
    return 0;
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:42:21: warning: unused variable 'j2' [-Wunused-variable]
   42 |     int n, k, i, j, j2, cur = 0, cnt = 0;
      |                     ^~
chorus.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
chorus.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf(" %s", s);
      |     ~~~~~^~~~~~~~~~

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Incorrect 1 ms 8536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Incorrect 1 ms 8536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Incorrect 1 ms 8536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Incorrect 1 ms 8536 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6592 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6488 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Incorrect 1 ms 8536 KB Output isn't correct
13 Halted 0 ms 0 KB -