General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
58182064 Practice:
icecuber
1070J - 29 GNU C++14 Accepted 202 ms 524 KB 2019-08-02 18:36:28 2019-08-02 18:36:28
 
 
→ Source
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll knapsack(int*c, int n, int m, int k, int last) {
  vector<int> dp(n+1,0);
  dp[0] = 1;
  for (int i = 0; i < 26; i++) {
    if (i == last) continue;
    for (int j = n-c[i]; j >= 0; j--)
      dp[j+c[i]] |= dp[j];
  }
  ll ans = 1e9;
  for (int i = n; i >= n-c[last] && i >= 0; i--) {
    if (dp[i]) {
      ll a = n-i;
      ll b = (i+c[last])-(k-m);
      ans = min(ans, a*b);
    }
  }
  return max(0ll,ans);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    string s;
    cin >> s;
    int c[26] = {};
    for (char ci : s)
      c[ci-'A']++;
    ll ans = n*m;
    for (int i = 0; i < 26; i++) {
      ans = min(ans, knapsack(c, n, m, k, i));
    }
    cout << ans << endl;
  }
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details