# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
127035939 |
Practice:
huansir |
1070J
- 29
|
C++14 (GCC 6-32)
|
Accepted
|
93 ms
|
4052 KB
|
2021-08-26 12:25:31 |
2021-08-26 12:25:31 |
|
#include <iostream>
#include <cstdio>
#include <bitset>
using namespace std;
int t;
int n, m, k;
char s[200010];
int tot[30];
bool dp[200010];
int main()
{
scanf("%d", &t);
while(t --)
{
scanf("%d%d%d", &n, &m, &k);
if(n < m)swap(n, m);
scanf("%s", s + 1);
for (int i = 0; i <= 26; ++ i)
tot[i] = 0;
for (int i = 1; i <= k; ++ i)
{
++ tot[s[i] - 'A'];
}
long long ans = 1e18;
for (int i = 0; i <= 25; ++ i)
{
for (int i = 1; i <= n; ++ i)
dp[i] = 0;
dp[0] = 1;
for (int j = 0; j <= 25; ++ j)
{
if(i == j)continue;
for (int i = n; i >= tot[j]; -- i)
dp[i] |= dp[i - tot[j]];
// cout << dp << endl;
}
for (int j = 0; j <= min(n, tot[i]); ++ j)
if(dp[n - j])
ans = min(ans, 1ll * j * (max(0, tot[i] - j - (k - n - m))));
}
printf("%lld\n", ans);
}
}
Click to see test details