QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#559284#2465. Where Have You Bin?Lavine#AC ✓1ms3960kbC++141.2kb2024-09-11 21:11:042024-09-11 21:11:06

Judging History

你现在查看的是最新测评结果

  • [2024-09-11 21:11:06]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3960kb
  • [2024-09-11 21:11:04]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=155;
char s[N],t[]="AEIOU";
int n,m,sum[N][N],dp[10][N],cnt[N],a[N],ans=1e9;
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x;
        scanf("%d",&x);
        a[x]=0,s[x]='X';
    }
    for(int i=1;i<=n;i++) {
        cnt[s[i]]++;
        for(int j=0;j<5;j++){
            if(s[i]==t[j])sum[t[j]][i]=sum[t[j]][i-1]+a[i];
            else sum[t[j]][i]=sum[t[j]][i-1];
        }
    }
    scanf("%s",s+1);
    for(int i=strlen(s+1);i;i--)cnt[s[i]]++;
    do{
        for(int i=0;i<=5;i++){
            for(int j=0;j<=n;j++){
                dp[i][j]=1e9;
            }
        }
        dp[0][0]=0;
        for(int i=0;i<=5;i++){
            char ch=t[i];
            for(int j=0;j<n;j++){
                dp[i][j+1]=min(dp[i][j],dp[i][j+1]);
                if(i<5&&j+cnt[ch]<=n){
                    dp[i+1][j+cnt[ch]]=min(dp[i+1][j+cnt[ch]],dp[i][j]+sum[ch][n]-sum[ch][j+cnt[ch]]+sum[ch][j]);
                }
            }
        }
        ans=min(ans,dp[5][n]);
    }while(next_permutation(t,t+5));
    printf("%d\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3772kb

input:

AEIOUU
1 4 6 9 2 3
1 6
A

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

AEIOUU
10 4 6 9 2 3
1 6
A

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

AEIOUU
1 4 6 9 2 3
4 5 1 4 3
EUE

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

A
100
0
X

output:

0

result:

ok single line: '0'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3812kb

input:

A
100
1 1
X

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

A
100
1 1
A

output:

0

result:

ok single line: '0'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3772kb

input:

A
100
1 1
U

output:

0

result:

ok single line: '0'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3768kb

input:

X
0
0
X

output:

0

result:

ok single line: '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

X
0
0
E

output:

0

result:

ok single line: '0'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3952kb

input:

AAEIOU
10 10 9 10 8 7
1 1
I

output:

8

result:

ok single line: '8'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

AAEIOU
10 10 8 10 9 7
1 1
I

output:

8

result:

ok single line: '8'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

AAEIOU
3 3 8 3 9 7
1 1
I

output:

6

result:

ok single line: '6'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3868kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 16 37 4...

output:

1519

result:

ok single line: '1519'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3744kb

input:

AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...

output:

933

result:

ok single line: '933'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3808kb

input:

AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...

output:

741

result:

ok single line: '741'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3872kb

input:

AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...

output:

421

result:

ok single line: '421'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3764kb

input:

AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...

output:

261

result:

ok single line: '261'

Test #18:

score: 0
Accepted
time: 0ms
memory: 3936kb

input:

AAEEIIOOUUX
1 1 30 100 30 100 30 100 30 100 0
0
A

output:

120

result:

ok single line: '120'

Test #19:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

AAEEIIOOUUXX
1 1 30 100 30 100 30 100 30 100 0 0
0
A

output:

120

result:

ok single line: '120'

Test #20:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

AAEEIIOOUUXXX
1 1 30 100 30 100 30 100 30 100 0 0 0
0
A

output:

2

result:

ok single line: '2'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3876kb

input:

AEIOUUUUUUU
11 1 2 3 4 5 6 7 8 9 10
3 6 8 10
AAA

output:

16

result:

ok single line: '16'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

UUUUUUUOIEA
10 9 8 7 6 5 4 3 2 1 11
3 2 4 6
AAA

output:

16

result:

ok single line: '16'

Test #23:

score: 0
Accepted
time: 1ms
memory: 3948kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 16 37 4...

output:

1739

result:

ok single line: '1739'

Test #24:

score: 0
Accepted
time: 1ms
memory: 3960kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 31 6 3 43 1 89 91 65 84 81 88 3 76 58 100 93 99 83 100 54 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 100 37 ...

output:

1668

result:

ok single line: '1668'

Test #25:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 26 3 76 58 50 93 70 99 83 100 66 2 85 68 43 74 90 61 1 88 60 1 92 71 83 33 79 85 6 9 16 37 4...

output:

495

result:

ok single line: '495'

Test #26:

score: 0
Accepted
time: 1ms
memory: 3852kb

input:

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 31 6 3 43 100 89 91 65 84 81 26 3 76 58 50 93 70 99 83 99 66 2 85 68 43 74 90 61 1 88 60 1 92 71 100 33 79 85 6 9 16 37 ...

output:

495

result:

ok single line: '495'

Test #27:

score: 0
Accepted
time: 1ms
memory: 3760kb

input:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0

result:

ok single line: '0'

Test #28:

score: 0
Accepted
time: 1ms
memory: 3952kb

input:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0

result:

ok single line: '0'

Test #29:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

0

result:

ok single line: '0'

Test #30:

score: 0
Accepted
time: 0ms
memory: 3956kb

input:

AAAAAAAAAAAAAAAAAAEEEEEEIIIIIIIIIIIOOOOUUUUUUUUUUU
20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 88 3 76 58 50 93 70 83 83 54 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9
39 11 39 7 24 44 34 20 23 25 29 49 31 17 37 45 22 9 18 14 2 41 35 16 36 26 13 40 5 43 42 28 21 48 8 19 12 38...

output:

0

result:

ok single line: '0'

Test #31:

score: 0
Accepted
time: 0ms
memory: 3948kb

input:

AAAAAAAAAAAXXXEEEEEEEEEXXXXIIIXXXOOOOOOOOOUUUUUXXX
14 84 66 62 55 24 5 67 22 97 59 0 0 0 86 67 61 71 86 22 98 4 42 0 0 0 0 13 77 70 0 0 0 60 81 94 68 69 40 71 13 5 55 30 74 99 60 0 0 0
21 35 6 36 11 39 38 8 34 2 22 21 16 15 40 47 18 7 44 4 3 37
OAEEAOUUUOUEIEUUAAOUUOEIEOIEOUOIOO

output:

206

result:

ok single line: '206'

Test #32:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

AAAAAAAAAEEEEEEEEEEEEIIIIIIIIIXXOOOOOOOOOOOOUUUUUU
16 37 44 20 5 42 100 56 49 96 33 28 54 60 12 7 31 43 20 87 81 74 99 74 98 42 4 52 86 73 0 0 5 83 1 98 86 54 85 8 11 46 12 94 39 90 17 37 18 64
32 21 20 35 41 13 12 7 40 26 39 6 45 47 15 2 25 19 34 3 27 29 11 49 1 33 36 23 38 5 46 8 43
AEIEIIOUUEAAUA...

output:

256

result:

ok single line: '256'

Test #33:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

AAAAAAAXEEEEEXXXXIIIIIIIIIOOOOOOOOOOUUUUUUUUUUUXXX
86 19 11 62 35 80 45 0 4 22 92 62 88 0 0 0 0 80 53 74 32 6 35 33 20 53 99 34 51 58 98 94 52 35 52 90 87 16 93 45 72 51 12 33 68 16 67 0 0 0
18 6 9 37 39 23 22 40 18 29 12 32 1 31 43 4 38 3 30
AIOAUOUIAU

output:

155

result:

ok single line: '155'

Test #34:

score: 0
Accepted
time: 0ms
memory: 3796kb

input:

AAAAAAAAAXXXEEEXXIIIIIIIIIIIIIXOOOOOOOOOOOUUUUUUUX
80 30 91 15 14 98 86 12 38 0 0 0 41 20 57 0 0 86 72 39 37 11 20 3 27 84 66 34 89 77 0 64 93 1 22 58 95 17 30 92 41 10 80 69 96 58 63 6 1 0
4 32 22 27 5
IOIUIUEA

output:

10

result:

ok single line: '10'

Test #35:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

AAAAAAAXXEEEEEEEEEEEEIIIIIIIIXXXXXOOOOOOOOUUUUUXXX
58 40 59 87 43 68 61 0 0 71 43 46 76 54 64 94 31 48 21 12 80 18 62 77 69 84 66 39 7 0 0 0 0 0 67 68 10 36 19 23 55 38 93 88 3 56 3 0 0 0
6 28 4 43 14 6 27
EEIIU

output:

61

result:

ok single line: '61'