oj.uz

답안 #250777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
250777 2020-07-19T06:20:31 Z dvdg6566 Mobitel (COCI19_mobitel) C++14
13 / 130
 3754 ms 26324 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 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);
	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
13.0 / 130.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 52 ms 11392 KB Output isn't correct
2 Correct 50 ms 11392 KB Output is correct
3 Incorrect 316 ms 18660 KB Output isn't correct
4 Incorrect 345 ms 19540 KB Output isn't correct
5 Incorrect 424 ms 19540 KB Output isn't correct
6 Incorrect 396 ms 19540 KB Output isn't correct
7 Incorrect 219 ms 17880 KB Output isn't correct
8 Incorrect 1897 ms 23508 KB Output isn't correct
9 Incorrect 3698 ms 26068 KB Output isn't correct
10 Incorrect 3754 ms 26324 KB Output isn't correct