oj.uz

Submission #250769

# Submission time Handle Problem Language Result Execution time Memory
250769 2020-07-19T05:59:13 Z dvdg6566 Mobitel (COCI19_mobitel) C++14
13 / 130
 369 ms 43732 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=310;
const ll MAXK=1000001;
const ll INF = 1e13;
const ll MOD = 1e9+7;

vi V;
ll R,C,N;
ll A[MAXN][MAXN];
ll mx[MAXK];
ll dp[MAXN][2][1010];

inline int ask(int x){
	if(x>=N)return SZ(V)-1;
	return mx[x];
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>R>>C>>N;
	for(int i=0;i<R;++i)for(int j=0;j<C;++j)cin>>A[i][j];

	for(int i=1;i<=N;++i)V.pb(N/i);
	sort(ALL(V));
	V.resize(unique(ALL(V))-V.begin());
	memset(mx,-1,sizeof(mx));
	for(int i=0;i<SZ(V);++i)mx[V[i]]=i;
	for(int i=1;i<=N;++i)if(mx[i]==-1)mx[i]=mx[i-1];
	ll m=1;
	for(int i=0;i<C;++i){
		m*=A[0][i];
		dp[i][0][ask(m)]=1;
	}
	bool t=1;

	for(int i=1;i<R;++i){
		for(int j=0;j<C;++j)for(int w=0;w<SZ(V);++w){
			dp[j][t][w]=0;
		}
		for(int j=0;j<C;++j)for(int w=0;w<SZ(V);++w){
			// for each dp[j][1^t][w]
			int x=ask(V[w]*A[i][j]);
			dp[j][t][x]+=dp[j][1^t][w];
			dp[j][t][x]%=MOD;
		}
		for(int j=0;j<C-1;++j)for(int w=0;w<SZ(V);++w){
			int x=ask(V[w]*A[i][j+1]);
			dp[j+1][t][x]+=dp[j][t][w];
			dp[j+1][t][x]%=MOD;
		}
		// cerr<<"Row "<<i<<'\n';
		// for(int j=0;j<C;++j){
		// 	cerr<<"Col "<<j<<'\n';
		// 	for(int w=0;w<SZ(V);++w){
		// 		if(!dp[j][t][w])continue;
		// 		cerr<<V[w]<<' ';
		// 		// cerr<<dp[j][t][w]<<' ';
		// 	}
		// 	cerr<<'\n';
		// }
		t^=1;
	}
	t^=1;
	cout<<dp[C-1][t][SZ(V)-1];
}

Subtask #1
13.0 / 130.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 11648 KB Output isn't correct
2 Correct 56 ms 11648 KB Output is correct
3 Incorrect 346 ms 17120 KB Output isn't correct
4 Incorrect 369 ms 18028 KB Output isn't correct
5 Runtime error 59 ms 36180 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 80 ms 36212 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 56 ms 31828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 300 ms 40608 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 71 ms 43476 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 74 ms 43732 KB Execution killed with signal 11 (could be triggered by violating memory limits)