记录编号	128551	评测结果	AAAAAA
题目名称	[Vocaloid]双子的混唱	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2014-10-17 21:01:14	内存使用	0.39 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
struct www{
	int shi,zuicd,mu;
	www(){shi=0;zuicd=0;mu=0;}
	bool operator<(const www&z) const {return zuicd<z.zuicd;}
} song[20];
vector<www> mi0,mi1,mi2;
vector<www>::iterator A;
int next[20010]={0},k,i,p,cd,h,j,zui=0,aiky=0,misaki=0,miku=0,n,m,t,zj1,zj2;
string s1,s2;
void get_next()
{
	memset(next,0,sizeof(next));j=0;
	for(i=1;i<cd;i++)
	{
		while(j&&(s1[j]!=s1[i]))j=next[j];
		if(s1[j]==s1[i])next[i+1]=++j;
		else next[i+1]=0;
	}
	j=0;zui=0;
	for(i=0;i<cd;i++)
	{
		while(j&&(s1[j]!=s2[i]))j=next[j];
		if(s1[j]==s2[i]){j++;if(j>zui)zui=j;}
	}
}
void init()
{
	cin>>s1;
	cin>>s2;
	s1.erase(0,h);
	s2.erase(0,h);
	cd=s1.size();
	get_next();
}
void vocaloid(int x,int xu)
{
	mi1.push_back(song[xu]);
	mi0.clear();mi0.insert(mi0.begin(),mi1.begin(),mi1.end());
	sort(mi0.begin(),mi0.end());
	p=0;aiky=0;
	for(A=mi0.begin();A!=mi0.end();A++){p++;aiky+=(*A).zuicd*p;}
	if(aiky>miku)
	{
		miku=aiky;
		mi2.clear();mi2.insert(mi2.begin(),mi0.begin(),mi0.end());
	}
	for(int e=xu+1;e<=n;e++)
	{
		zj1=x+song[e].shi;
		if(zj1<=t) vocaloid(zj1,e);
	}
	mi1.pop_back();
}
int main()
{
	freopen("rinlen.in","r",stdin);
	freopen("rinlen.out","w",stdout);
	scanf("%d%d%d\n",&n,&m,&t);
	for(int w=1;w<=n;w++)
	{
		song[w].mu=w;
		scanf("%d%d\n",&h,&song[w].shi);
		init();
		song[w].zuicd=zui;
	}
	for(i=1;i<=n;i++) aiky+=song[i].shi;
	if(aiky<=t)
	{
		sort(song+1,song+(n+1));
		aiky=0;
		for(i=1;i<=n;i++)aiky+=i*song[i].zuicd;
		if(aiky<m) printf("QwQ\n");
		else
		{
			printf("%d %d\n",n,aiky);
			for(i=1;i<n;i++)printf("%d ",song[i].mu);
			printf("%d\n",song[n].mu);
		}
	}
	else
	{
		for(i=1;i<=n;i++)
		{
			if(song[i].shi<=t)
			vocaloid(song[i].shi,i);
			mi1.clear();
		}
		if(miku<m) printf("QwQ\n");
		else
		{
			misaki=mi2.size(); 
			printf("%d %d\n",misaki,miku);
			for(A=mi2.begin();A!=mi2.end();A++)
			printf("%d ",(*A).mu);
			printf("\n");
		}
	}
	return 0;
}