oj.uz

Submission #159819

# Submission time Handle Problem Language Result Execution time Memory
159819 2019-10-24T22:59:19 Z theknife2001 Mobitel (COCI19_mobitel) C++17
26 / 130
 289 ms 2808 KB 
#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.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 2808 KB Output is correct
2 Correct 289 ms 2808 KB Output is correct
3 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)