oj.uz

Submission #250773

# Submission time Handle Problem Language Result Execution time Memory
250773 2020-07-19T06:09:50 Z dvdg6566 Mobitel (COCI19_mobitel) C++14
13 / 130
 379 ms 47520 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(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.0 / 130.0

# Verdict Execution time Memory Grader output
1 Incorrect 55 ms 11392 KB Output isn't correct
2 Correct 54 ms 11392 KB Output is correct
3 Incorrect 350 ms 18652 KB Output isn't correct
4 Incorrect 379 ms 19540 KB Output isn't correct
5 Runtime error 63 ms 36948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 93 ms 39380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 58 ms 34260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 285 ms 47520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 80 ms 45652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 83 ms 46036 KB Execution killed with signal 11 (could be triggered by violating memory limits)