Submission #250773

#	Time	Username	Problem	Language	Result	Execution time	Memory
250773		dvdg6566	Mobitel (COCI19_mobitel)	C++14	13 / 130	379 ms	47520 KiB

mobitel

#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][2010];

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];
		if(m>N)m=N;
		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 / 130