比赛 |
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);
}
}