?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
44733500 |
Practice: Jayson_jun |
1070J - 29 | C++14 (GCC 6-32) | Accepted | 156 ms | 992 KB | 2018-10-23 14:47:00 | 2018-10-23 14:47:00 |
#include<bits/stdc++.h> using namespace std; const int maxn = 2*1e5+5; int t; int n,m,k; char s[maxn]; int a[30]; int dp[maxn]; int main() { scanf("%d",&t); while(t--) { scanf("%d%d%d", &n, &m, &k); scanf("%s", s); for (int i = 0; i < 26; i++) a[i] = 0; for (int i = 0; i < k; i++) a[(int)(s[i] - 'A')]++; int ans = n * m; for (int p = 0; p < 26; p++) { for (int i = 0; i <= k; i++) dp[i] = 0; dp[0] = 1; for (int i = 0; i < 26; i++) { if (i == p) continue; for (int j = k; j >= a[i]; j--) { if(dp[j-a[i]]) dp[j]=1; } } for (int i = 0; i <= k; i++) { if (!dp[i]) continue; int x = max(0, n - i); int y = max(0, m - (k - a[p] - i)); if (x + y > a[p]) continue; ans = min(ans, x * y); } } printf("%d\n",ans); } return 0; }
?
?
?
?