Submission #159922

#	Time	Username	Problem	Language	Result	Execution time	Memory
159922		theknife2001	Mobitel (COCI19_mobitel)	C++17	0 / 130	3603 ms	65536 KiB

mobitel

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N=105;
const int mod=1e9+7;
ll dp[2][N][21][14][10][10];
ll a[N][N];
int n,m,M;

ll pow(int x , int n)
{
	ll ret=1;
	for(int i=0;i<n;i++)
	ret*=x;
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>M;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	}
	if(a[0][0]==1)
	dp[0][0][0][0][0][0]=1;
	if(a[0][0]==2)
	dp[0][0][1][0][0][0]=1;
	if(a[0][0]==3)
	dp[0][0][0][1][0][0]=1;
	if(a[0][0]==4)
	dp[0][0][2][0][0][0]=1;
	if(a[0][0]==5)
	dp[0][0][0][0][1][0]=1;
	if(a[0][0]==6)
	dp[0][0][1][1][0][0]=1;
	if(a[0][0]==7)
	dp[0][0][0][0][0][1]=1;
	if(a[0][0]==8)
	dp[0][0][3][0][0][0]=1;
	if(a[0][0]==9)
	dp[0][0][0][2][0][0]=1;
	if(a[0][0]==10)
	dp[0][0][1][0][1][0]=1;
	
	int cnt1,cnt2;
	for(int I=0;I<n;I++)
	{
		int i=I%2;
		for(int j=0;j<m;j++)
		{
			if(I==0&&j==0)
			continue ;
			cnt1=cnt2=0;
			for(int to=3;to<11;to*=3)
			if(a[I][j]%to==0)
			cnt2++;
			for(int to=2;to<11;to*=2)
			if(a[I][j]%to==0)
			cnt1++;
			for(int to=0;to<21;to++)
				for(int th=0;th<14;th++)
					for(int fi=0;fi<10;fi++)
						for(int se=0;se<10;se++)
							dp[i][j][to][th][fi][se]=0;
			for(int to=0;to<21;to++)
			{
				for(int th=0;th<14;th++)
				{
					for(int fi=0;fi<10;fi++)
					{
						for(int se=0;se<10;se++)
						{
							if(I)
								if(dp[i^1][j][to][th][fi][se])
								{
									dp[i][j][min(to+cnt1,20)][min(cnt2+th,13)][min(fi+(int)(a[I][j]%5==0),9)][min(se+(int)(a[I][j]%7==0),9)]+=dp[i^1][j][to][th][fi][se];
								}
							if(j)
								if(dp[i][j-1][to][th][fi][se])
								{
									dp[i][j][min(to+cnt1,20)][min(cnt2+th,13)][min(fi+(int)(a[I][j]%5==0),9)][min(se+(int)(a[I][j]%7==0),9)]+=dp[i][j-1][to][th][fi][se];
								}
						}
					}	
				}
			}
			for(int to=0;to<21;to++)
			{
				for(int th=0;th<14;th++)
				{
					for(int fi=0;fi<10;fi++)
					{
						for(int se=0;se<10;se++)
						{
							dp[i][j][to][th][fi][se]%=mod;
						}
					}
				}
			}	
				
		}
	}
	ll sum=1;
	ll ans=0;
	for(int to=0;to<21;to++)
	{
		for(int th=0;th<14;th++)
		{
			for(int fi=0;fi<10;fi++)
			{
				for(int se=0;se<10;se++)
				{
					sum=pow(2,to)*pow(3,th);
					ans%=mod;
					if(sum>=M)
					{
						ans+=dp[(n-1)%2][m-1][to][th][fi][se];;
						continue ;
					}
					sum*=pow(5,fi);
					if(sum>=M)
					{
						ans+=dp[(n-1)%2][m-1][to][th][fi][se];
						continue ;
					}
					sum*=pow(7,se);
					if(sum>=M)
					{
						ans+=dp[(n-1)%2][m-1][to][th][fi][se];
						continue ;
					}
				}
			}
		}
	}
	cout<<ans<<endl;			
	return 0;
}

• Subtask 1: 0 / 130