QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #559284 | #2465. Where Have You Bin? | Lavine# | AC ✓ | 1ms | 3960kb | C++14 | 1.2kb | 2024-09-11 21:11:04 | 2024-09-11 21:11:06 |
Judging History
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;
}
详细
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'