General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
44584892 Contestant:
肥修赛大象,只是给给短。: jiangIy, sagitta_luminis, wxh010910
1070J - 29 GNU C++11 Happy New Year! 62 ms 1784 KB 2018-10-20 12:19:06 2018-10-20 12:19:06
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int T,a[30],n,m,K,f[201000],g[201000];
char s[201000];
void sol(){
	scanf("%d%d%d",&n,&m,&K);
	scanf("%s",s+1);
	memset(a,0,sizeof(a));
	for(int i=1;i<=K;++i)a[s[i]-'A'+1]++;
	for(int j=0;j<=K;++j)f[j]=g[j]=inf;
	f[0]=0;
	long long ans=(long long)1e18;
	for(int i=1;i<=26;++i){
		for(int j=0;j<=K;++j)g[j]=f[j];
		for(int j=i+1;j<=26;++j)
			for(int k=K;k>=a[j];--k)
				g[k]=min(g[k],g[k-a[j]]+a[j]);
		for(int k=K-1;k>=0;--k)g[k]=min(g[k],g[k+1]);
		for(int j=0;j<=a[i];++j){
			int lef=j,rig=a[i]-j;
			if(lef<=n&&g[n-lef]!=inf&&K-a[i]-g[n-lef]+rig>=m)
				ans=min(ans,(long long)lef*max(0,m-(K-a[i]-g[n-lef])));
		}
		for(int k=K;k>=a[i];--k)
			f[k]=min(f[k],f[k-a[i]]+a[i]);
	}
	printf("%lld\n",ans);
}
int main(){
	scanf("%d",&T);
	while(T--)sol();
} 
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details