# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
44952060 |
Practice:
BARPITF |
1070J
- 29
|
C++17 (GCC 7-32)
|
Accepted
|
93 ms
|
480 KB
|
2018-10-27 15:34:50 |
2018-10-27 15:34:50 |
|
#include<cstdio>
#include<iostream>
const int N=3e4+5,M=2e5+5;
bool dp[N];int num[26];
int n,m,k;char s[M];
int check(int v) {
for(int i=1;i<=n;i++) dp[i]=0;
dp[0]=1;int ans=n*m;
for(int i=0;i<26;i++) {
if(i==v) continue;
for(int j=n;j>=num[i];j--) dp[j]=dp[j]||dp[j-num[i]];
}
int t=k-n-m;
for(int i=0;i<=n;i++) if(dp[i]&&i+num[v]>=n) ans=std::min(ans,(n-i)*std::max(num[v]-n+i-t,0));
return ans;
}
int main() {
int T;scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&m,&k);
scanf("%s",s);for(int i=0;i<26;i++) num[i]=0;
for(int i=0;i<k;i++) num[s[i]-'A']++;
int ans=n*m;
for(int i=0;i<26;i++) ans=std::min(ans,check(i));
printf("%d\n",ans);
}
return 0;
}
Click to see test details