General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
54563722 Practice:
wangrq
1070J - 29 GNU C++17 Accepted 124 ms 3608 KB 2019-05-24 18:16:25 2019-05-24 18:16:25
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
int t,n,m,q,dp[27][31001],cnt[27];
char s[330001];
void update(int &a,int b){if(a<b)a=b;}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%s",&n,&m,&q,s);
		memset(cnt,0,sizeof cnt);
		for(int i=0;i<q;i++)cnt[s[i]-'A'+1]++;
		int ans=1<<30;
		for(int k=1;k<=26;k++)
		{
			swap(cnt[k],cnt[26]);
			for(int i=0;i<26;i++)
				for(int j=0;j<=n;j++)dp[i][j]=-1;
			dp[0][0]=0;
			for(int i=0;i<25;i++)
				for(int j=0;j<=n;j++)
					if(dp[i][j]!=-1)
					{
						update(dp[i+1][j],dp[i][j]+cnt[i+1]);
						update(dp[i+1][min(n,j+cnt[i+1])],dp[i][j]);
					}
			for(int i=0;i<=n;i++)
				if(dp[25][i]!=-1&&n-i+max(0,m-dp[25][i])<=cnt[26])ans=min(ans,(n-i)*max(0,m-dp[25][i]));
			swap(cnt[k],cnt[26]);
		}
		printf("%d\n",ans);
	}
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details