oj.uz

Submission #1037906

# Submission time Handle Problem Language Result Execution time Memory
1037906 2024-07-29T09:59:06 Z 정희우(#10983) Chorus (JOI23_chorus) C++17
16 / 100
 73 ms 98900 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using intp = pair<int,int>;
using vint = vector<int>;

const int MAX_N=5010;

int n,k;
char str[MAX_N<<1];
int ord[MAX_N<<1];
vint pos[2];
int cnta[MAX_N<<1];
int cntb[MAX_N<<1];
int suma[MAX_N<<1];
lint ans;
int dt[MAX_N][MAX_N];

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> k >> str;
    for(int i=0;i<n*2;i++)
    {
        ord[i]=pos[str[i]=='B'].size();
        pos[str[i]=='B'].push_back(i);
    }
    for(int i=0;i<n;i++)
    {
        while(pos[0][i]>pos[1][i])
        {
            int p=pos[0][i];
            swap(pos[0][ord[p]],pos[1][ord[p-1]]);
            swap(ord[p],ord[p-1]);
            swap(str[p],str[p-1]);
            ans++;
        }
    }
    for(int i=0;i<n*2;i++)
    {
        cnta[i]=(str[i]=='A')+cnta[max(0,i-1)];
        cntb[i]=(str[i]=='B')+cntb[max(0,i-1)];
        suma[i]=(str[i]=='A')*cntb[i]+suma[max(0,i-1)];
    }
    fill(dt[0],dt[0]+MAX_N*MAX_N,MAX_N*MAX_N);
    dt[0][0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            for(int l=1;l<=k;l++)
                dt[i][l]=min(dt[i][l],dt[j][l-1]+max(0,suma[pos[0][i-1]]-suma[pos[1][j]]-(cntb[pos[1][j]]-1)*(i-cnta[pos[1][j]])));
    cout << ans+dt[n][k];
    return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 98652 KB Output is correct
2 Correct 17 ms 98564 KB Output is correct
3 Correct 18 ms 98900 KB Output is correct
4 Correct 24 ms 98640 KB Output is correct
5 Correct 18 ms 98648 KB Output is correct
6 Correct 17 ms 98648 KB Output is correct
7 Correct 29 ms 98652 KB Output is correct
8 Correct 18 ms 98652 KB Output is correct
9 Correct 28 ms 98640 KB Output is correct
10 Correct 28 ms 98652 KB Output is correct
11 Correct 28 ms 98644 KB Output is correct
12 Correct 19 ms 98652 KB Output is correct
13 Correct 18 ms 98648 KB Output is correct
14 Correct 19 ms 98604 KB Output is correct
15 Correct 18 ms 98652 KB Output is correct
16 Correct 18 ms 98648 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 98652 KB Output is correct
2 Correct 17 ms 98564 KB Output is correct
3 Correct 18 ms 98900 KB Output is correct
4 Correct 24 ms 98640 KB Output is correct
5 Correct 18 ms 98648 KB Output is correct
6 Correct 17 ms 98648 KB Output is correct
7 Correct 29 ms 98652 KB Output is correct
8 Correct 18 ms 98652 KB Output is correct
9 Correct 28 ms 98640 KB Output is correct
10 Correct 28 ms 98652 KB Output is correct
11 Correct 28 ms 98644 KB Output is correct
12 Correct 19 ms 98652 KB Output is correct
13 Correct 18 ms 98648 KB Output is correct
14 Correct 19 ms 98604 KB Output is correct
15 Correct 18 ms 98652 KB Output is correct
16 Correct 18 ms 98648 KB Output is correct
17 Correct 24 ms 98652 KB Output is correct
18 Correct 36 ms 98652 KB Output is correct
19 Incorrect 73 ms 98636 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 98652 KB Output is correct
2 Correct 17 ms 98564 KB Output is correct
3 Correct 18 ms 98900 KB Output is correct
4 Correct 24 ms 98640 KB Output is correct
5 Correct 18 ms 98648 KB Output is correct
6 Correct 17 ms 98648 KB Output is correct
7 Correct 29 ms 98652 KB Output is correct
8 Correct 18 ms 98652 KB Output is correct
9 Correct 28 ms 98640 KB Output is correct
10 Correct 28 ms 98652 KB Output is correct
11 Correct 28 ms 98644 KB Output is correct
12 Correct 19 ms 98652 KB Output is correct
13 Correct 18 ms 98648 KB Output is correct
14 Correct 19 ms 98604 KB Output is correct
15 Correct 18 ms 98652 KB Output is correct
16 Correct 18 ms 98648 KB Output is correct
17 Correct 24 ms 98652 KB Output is correct
18 Correct 36 ms 98652 KB Output is correct
19 Incorrect 73 ms 98636 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 98652 KB Output is correct
2 Correct 17 ms 98564 KB Output is correct
3 Correct 18 ms 98900 KB Output is correct
4 Correct 24 ms 98640 KB Output is correct
5 Correct 18 ms 98648 KB Output is correct
6 Correct 17 ms 98648 KB Output is correct
7 Correct 29 ms 98652 KB Output is correct
8 Correct 18 ms 98652 KB Output is correct
9 Correct 28 ms 98640 KB Output is correct
10 Correct 28 ms 98652 KB Output is correct
11 Correct 28 ms 98644 KB Output is correct
12 Correct 19 ms 98652 KB Output is correct
13 Correct 18 ms 98648 KB Output is correct
14 Correct 19 ms 98604 KB Output is correct
15 Correct 18 ms 98652 KB Output is correct
16 Correct 18 ms 98648 KB Output is correct
17 Correct 24 ms 98652 KB Output is correct
18 Correct 36 ms 98652 KB Output is correct
19 Incorrect 73 ms 98636 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 98652 KB Output is correct
2 Correct 17 ms 98564 KB Output is correct
3 Correct 18 ms 98900 KB Output is correct
4 Correct 24 ms 98640 KB Output is correct
5 Correct 18 ms 98648 KB Output is correct
6 Correct 17 ms 98648 KB Output is correct
7 Correct 29 ms 98652 KB Output is correct
8 Correct 18 ms 98652 KB Output is correct
9 Correct 28 ms 98640 KB Output is correct
10 Correct 28 ms 98652 KB Output is correct
11 Correct 28 ms 98644 KB Output is correct
12 Correct 19 ms 98652 KB Output is correct
13 Correct 18 ms 98648 KB Output is correct
14 Correct 19 ms 98604 KB Output is correct
15 Correct 18 ms 98652 KB Output is correct
16 Correct 18 ms 98648 KB Output is correct
17 Correct 24 ms 98652 KB Output is correct
18 Correct 36 ms 98652 KB Output is correct
19 Incorrect 73 ms 98636 KB Output isn't correct
20 Halted 0 ms 0 KB -