oj.uz

Submission #250774

# Submission time Handle Problem Language Result Execution time Memory
250774 2020-07-19T06:10:26 Z dvdg6566 Mobitel (COCI19_mobitel) C++14
13 / 130
 4132 ms 26328 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][2010];

inline int 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(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.0 / 130.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 11392 KB Output isn't correct
2 Correct 54 ms 11504 KB Output is correct
3 Incorrect 336 ms 18648 KB Output isn't correct
4 Incorrect 370 ms 19540 KB Output isn't correct
5 Incorrect 438 ms 19540 KB Output isn't correct
6 Incorrect 409 ms 19552 KB Output isn't correct
7 Incorrect 214 ms 17764 KB Output isn't correct
8 Incorrect 1974 ms 23512 KB Output isn't correct
9 Incorrect 3874 ms 26068 KB Output isn't correct
10 Incorrect 4132 ms 26328 KB Output isn't correct