Submission #159819

#	Time	Username	Problem	Language	Result	Execution time	Memory
159819		theknife2001	Mobitel (COCI19_mobitel)	C++17	26 / 130	289 ms	2808 KiB

mobitel

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

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

int main()
{
	ios::sync_with_stdio(false);
	cin>>n>>m>>M;
	if(M>300)
	assert(0);
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
			cin>>a[i][j];
	}
	ll pre=1;
	for(int j=0;j<m;j++)
	{
		pre*=a[0][j];
		if(pre>M)
		pre=M;
		dp[0][j][pre]=1;
	}
	for(int I=1;I<n;I++)
	{
		int i=I%2;
		pre=1;
		for(int j=0;j<m;j++)
		{
			for(int k=0;k<=M;k++)dp[i][j][k]=0;
			for(int k=0;k<=M;k++)
			{
				
				if(dp[i^1][j][k])
				{
					
					dp[i][j][min((ll)M,a[I][j]*k)]+=dp[i^1][j][k];
				}
			}
			if(j-1>=0)
			{
				for(int k=0;k<=M;k++)
				{
					if(dp[i][j-1][k])
					{
						dp[i][j][min((ll)M,a[I][j]*k)]+=dp[i][j-1][k];
						
					}
				}
			}
			for(int k=0;k<=M;k++)
			dp[i][j][k]%=mod;
		}
	}
	cout<<dp[(n-1)%2][m-1][M]<<endl;
	return 0;
}

• Subtask 1: 26 / 130