Submission #25256379

Source Code Expand

#include<stdio.h>
const int maxn=25,maxm=10005,maxk=1<<20,maxa=2000005,mod=998244353;
int n,m,minn,ans;
int a[maxn],b[maxm],c[maxn][maxm],v[maxm],used[maxa],fac[maxa],nfac[maxa],inv[maxa],s[maxk],d[maxk];//supply & demand
inline int C(int n,int m){
	return n<m? 0:1ll*fac[n]*nfac[m]%mod*nfac[n-m]%mod;
}
inline int min(int a,int b){
	return a<b? a:b;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]),s[1<<(i-1)]=a[i];
	for(int i=1;i<=m;i++)
		scanf("%d",&b[i]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&c[i][j]),v[j]+=(c[i][j]<<(i-1));
	for(int i=1;i<=m;i++)
		d[v[i]]+=b[i];
	for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)
			if((j>>i)&1)
				s[j]+=s[j^(1<<i)],d[j]+=d[j^(1<<i)];
	fac[0]=fac[1]=nfac[0]=nfac[1]=inv[1]=1;
	for(int i=2;i<=s[(1<<n)-1];i++){
		fac[i]=1ll*fac[i-1]*i%mod;
		inv[i]=mod-1ll*(mod/i)*inv[mod%i]%mod;
		nfac[i]=1ll*nfac[i-1]*inv[i]%mod;
	}
	minn=1000000000;
	for(int i=1;i<(1<<n);i++)
		if(d[i])
			minn=min(minn,s[i]-d[i]);
	if(minn<0){
		puts("0 1");
		return 0;
	}
	printf("%d ",minn+1);
	for(int i=1;i<(1<<n);i++)
		if(s[i]-d[i]==minn)
			used[i]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<(1<<n);j++)
			if((j>>i)&1)
				used[j^(1<<i)]+=used[j];
	for(int i=1;i<(1<<n);i++)
		if(s[i]-d[i]==minn&&used[i]==1)
			ans=(ans+C(s[i],minn+1))%mod;
	printf("%d\n",ans);
	return 0;
}

Submission Info

Submission Time
Task H - Cabbage Master
User xiaoziyao
Language C++ (Clang 10.0.0)
Score 600
Code Size 1408 Byte
Status AC
Exec Time 100 ms
Memory 39764 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 73
Set Name Test Cases
Sample example0.txt, example1.txt, example2.txt
All 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, 020.txt, 021.txt, 022.txt, 023.txt, 024.txt, 025.txt, 026.txt, 027.txt, 028.txt, 029.txt, 030.txt, 031.txt, 032.txt, 033.txt, 034.txt, 035.txt, 036.txt, 037.txt, 038.txt, 039.txt, 040.txt, 041.txt, 042.txt, 043.txt, 044.txt, 045.txt, 046.txt, 047.txt, 048.txt, 049.txt, 050.txt, 051.txt, 052.txt, 053.txt, 054.txt, 055.txt, 056.txt, 057.txt, 058.txt, 059.txt, 060.txt, 061.txt, 062.txt, 063.txt, 064.txt, 065.txt, 066.txt, 067.txt, 068.txt, 069.txt, example0.txt, example1.txt, example2.txt
Case Name Status Exec Time Memory
000.txt AC 95 ms 38980 KiB
001.txt AC 86 ms 39024 KiB
002.txt AC 52 ms 22496 KiB
003.txt AC 69 ms 28896 KiB
004.txt AC 63 ms 26580 KiB
005.txt AC 52 ms 22280 KiB
006.txt AC 65 ms 26396 KiB
007.txt AC 89 ms 38876 KiB
008.txt AC 88 ms 39044 KiB
009.txt AC 55 ms 24800 KiB
010.txt AC 69 ms 26604 KiB
011.txt AC 65 ms 25224 KiB
012.txt AC 42 ms 20944 KiB
013.txt AC 65 ms 25368 KiB
014.txt AC 90 ms 38832 KiB
015.txt AC 88 ms 38844 KiB
016.txt AC 52 ms 22660 KiB
017.txt AC 70 ms 28092 KiB
018.txt AC 63 ms 25912 KiB
019.txt AC 53 ms 21780 KiB
020.txt AC 64 ms 26104 KiB
021.txt AC 86 ms 38860 KiB
022.txt AC 89 ms 38832 KiB
023.txt AC 69 ms 28296 KiB
024.txt AC 67 ms 28064 KiB
025.txt AC 71 ms 29672 KiB
026.txt AC 57 ms 25388 KiB
027.txt AC 73 ms 29804 KiB
028.txt AC 88 ms 38888 KiB
029.txt AC 87 ms 38816 KiB
030.txt AC 48 ms 21664 KiB
031.txt AC 72 ms 29864 KiB
032.txt AC 67 ms 28296 KiB
033.txt AC 52 ms 24172 KiB
034.txt AC 71 ms 28460 KiB
035.txt AC 50 ms 22056 KiB
036.txt AC 57 ms 21572 KiB
037.txt AC 39 ms 17392 KiB
038.txt AC 57 ms 21368 KiB
039.txt AC 55 ms 24436 KiB
040.txt AC 62 ms 25184 KiB
041.txt AC 46 ms 21120 KiB
042.txt AC 62 ms 25128 KiB
043.txt AC 26 ms 8648 KiB
044.txt AC 9 ms 6680 KiB
045.txt AC 14 ms 7160 KiB
046.txt AC 27 ms 13384 KiB
047.txt AC 11 ms 4676 KiB
048.txt AC 50 ms 19048 KiB
049.txt AC 76 ms 25712 KiB
050.txt AC 83 ms 29476 KiB
051.txt AC 85 ms 31404 KiB
052.txt AC 90 ms 33772 KiB
053.txt AC 83 ms 30804 KiB
054.txt AC 80 ms 28908 KiB
055.txt AC 84 ms 35520 KiB
056.txt AC 100 ms 39764 KiB
057.txt AC 2 ms 3112 KiB
058.txt AC 67 ms 18576 KiB
059.txt AC 65 ms 18396 KiB
060.txt AC 65 ms 18328 KiB
061.txt AC 66 ms 18096 KiB
062.txt AC 63 ms 17992 KiB
063.txt AC 65 ms 17860 KiB
064.txt AC 64 ms 17712 KiB
065.txt AC 63 ms 17780 KiB
066.txt AC 65 ms 17496 KiB
067.txt AC 64 ms 17376 KiB
068.txt AC 63 ms 17288 KiB
069.txt AC 65 ms 17160 KiB
example0.txt AC 2 ms 3096 KiB
example1.txt AC 2 ms 3028 KiB
example2.txt AC 2 ms 3100 KiB