比赛 20241125 评测结果 AAAAAAAAA
题目名称 夏娜的菠萝包 最终得分 100
用户昵称 wdsjl 运行时间 0.096 s
代码语言 C++ 内存使用 5.24 MiB
提交时间 2024-11-25 10:05:42
显示代码纯文本
#include <bits/stdc++.h> 
#define ll long long
const int N = 22; 
using namespace std;
int n,m,T,x,a[N][N],t[N],d[N],k[N],st[N],mt[N],e[N],f[N][20000],now,bz,tot,ans,inf;
char c;
int main(){
	freopen("shana.in","r",stdin);
	freopen("shana.out","w",stdout);
	while(1){
		scanf("%d",&n);
		if(!n) return 0;
		memset(f,-127,sizeof f);inf=f[0][0];
		f[0][0]=ans=0;
		for(int i=1;i<=n;i++)scanf("%d%d",&t[i],&d[i]);
		scanf("%d",&m);
		for(int i=1;i<=m;i++){
			st[i]=mt[i]=0;
			scanf("%d%d",&k[i],&e[i]);
			for(int j=1;j<=k[i];j++){
				scanf("%d",&a[i][j]);
				st[i]|=(1<<a[i][j]-1);
				mt[i]=max(mt[i],t[a[i][j]]/d[a[i][j]]+1);
			}
		}
		for(int i=0;i<=min(n,m)-1;i++){
			for(int S=0;S<=(1<<n)-1;S++)if(f[i][S]>=0){
				for(int l=1;l<=m;l++){
					if((st[l]&S)||mt[l]<i+1) continue;
					T=now=0;
					for(int j=1;j<=k[l];j++){
						T|=(1<<a[l][j]-1);
						now+=t[a[l][j]]-d[a[l][j]]*i;
					}
					f[i+1][S+T]=max(f[i+1][S+T],f[i][S]+now+e[l]);
					ans=max(ans,f[i+1][S+T]);
				}
			}
		}
		printf("%d\n",ans);
	}
}