Submission #250774

#TimeUsernameProblemLanguageResultExecution timeMemory
250774dvdg6566Mobitel (COCI19_mobitel)C++14
13 / 130
4132 ms26328 KiB
#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]; }
#Verdict Execution timeMemoryGrader output
Fetching results...