oj.uz

Submission #250778

# Submission time Handle Problem Language Result Execution time Memory
250778 2020-07-19T06:22:01 Z dvdg6566 Mobitel (COCI19_mobitel) C++14
130 / 130
 5114 ms 38976 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][3010];

inline ll ask(ll 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(ll i=0;i<R;++i)for(ll j=0;j<C;++j)cin>>A[i][j];

	for(ll i=1;i<=N;++i){
		V.pb(N/i);
		V.pb(N/i+1);
	}
	sort(ALL(V));
	V.resize(unique(ALL(V))-V.begin());

	memset(mx,-1,sizeof(mx));
	for(ll i=0;i<SZ(V);++i)mx[V[i]]=i;
	for(ll i=1;i<=N;++i)if(mx[i]==-1)mx[i]=mx[i-1];
	ll m=1;
	for(ll i=0;i<C;++i){
		m*=A[0][i];
		if(m>N)m=N;
		dp[i][0][ask(m)]=1;
	}
	int t=1;

	for(ll i=1;i<R;++i){
		for(ll j=0;j<C;++j)for(ll w=0;w<SZ(V);++w){
			dp[j][t][w]=0;
		}
		for(ll j=0;j<C;++j)for(ll w=0;w<SZ(V);++w){
			// for each dp[j][1^t][w]
			ll x=ask(V[w]*A[i][j]);
			dp[j][t][x]+=dp[j][1^t][w];
			dp[j][t][x]%=MOD;
		}
		for(ll j=0;j<C-1;++j)for(ll w=0;w<SZ(V);++w){
			ll 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(ll j=0;j<C;++j){
		// 	cerr<<"Col "<<j<<'\n';
		// 	for(ll 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
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11520 KB Output is correct
2 Correct 72 ms 11600 KB Output is correct
3 Correct 463 ms 27204 KB Output is correct
4 Correct 496 ms 28864 KB Output is correct
5 Correct 611 ms 28884 KB Output is correct
6 Correct 556 ms 28864 KB Output is correct
7 Correct 307 ms 26048 KB Output is correct
8 Correct 2588 ms 34752 KB Output is correct
9 Correct 5043 ms 38464 KB Output is correct
10 Correct 5114 ms 38976 KB Output is correct