답안 #159922

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
159922 2019-10-25T12:11:20 Z theknife2001 Mobitel (COCI19_mobitel) C++17
0 / 130
3603 ms 65536 KB
#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;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 148 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 150 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 3541 ms 46516 KB Output isn't correct
4 Incorrect 3603 ms 46508 KB Output isn't correct
5 Incorrect 3578 ms 46512 KB Output isn't correct
6 Incorrect 3583 ms 46504 KB Output isn't correct
7 Incorrect 1646 ms 32680 KB Output isn't correct
8 Runtime error 145 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 152 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 153 ms 65536 KB Execution killed with signal 11 (could be triggered by violating memory limits)