oj.uz

Submission #250771

# Submission time Handle Problem Language Result Execution time Memory
250771 2020-07-19T06:01:10 Z dvdg6566 Mobitel (COCI19_mobitel) C++14
26 / 130
 6000 ms 63572 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 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(i);
	// 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
26.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 388 ms 12544 KB Output is correct
2 Correct 406 ms 12672 KB Output is correct
3 Execution timed out 6052 ms 27236 KB Time limit exceeded
4 Execution timed out 6053 ms 28936 KB Time limit exceeded
5 Runtime error 299 ms 58320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Execution timed out 6071 ms 29012 KB Time limit exceeded
7 Runtime error 44 ms 31828 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 2902 ms 63152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 1175 ms 63444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 1688 ms 63572 KB Execution killed with signal 11 (could be triggered by violating memory limits)