Submission #1120078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1120078		fyan	Mobitel (COCI19_mobitel)	C++14	91 / 130	6055 ms	27288 KiB

mobitel

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define int long long

const int mxn = 305;
const int mod = 1e9+7;

int ksm(int a, int b = mod-2) {
	int res=1, aux=a;
	for (int i=1; i<=b; i*=2) {
		if (i&b) res=res*aux%mod;
		aux=aux*aux%mod;
	}
	return res;
}

int ft[2*mxn],ift[2*mxn];

int nck(int n, int k) {
	return ft[n]*ift[k]%mod*ift[n-k]%mod;
}

int r,c,n,g[mxn][mxn];
map<int,int> dp[mxn*mxn];

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
	ft[0] = ift[0] = 1;
	for (int i=1; i<2*mxn; i++) {
		ft[i] = i*ft[i-1]%mod;
		ift[i] = ksm(ft[i]);
	}
	
	cin>>r>>c>>n; n--;
	
	for (int i=0; i<r; i++) {
		for (int j=0; j<c; j++) {
			cin>>g[i][j];
		}
	}
		
	cin>>r>>c>>n;
	dp[0][n/g[0][0]]++;
	
	for (int i=0; i<r; i++) {
		for (int j=0; j<c; j++) {
			if (i<r-1) {
				for (auto [v,amt] : dp[i*mxn+j]) {
					dp[(i+1)*mxn+j][v/g[i+1][j]] += amt;
					dp[(i+1)*mxn+j][v/g[i+1][j]] %= mod;
				}
			}
			if (j<c-1) {
				for (auto [v,amt] : dp[i*mxn+j]) {
					dp[i*mxn+j+1][v/g[i][j+1]] += amt;
					dp[i*mxn+j+1][v/g[i][j+1]] %= mod;
				}
			}
			if (i!=r-1 || j!=c-1) dp[i*mxn+j].clear();
		}
	}
	
	int cnt = 0;
	for (auto [v,amt] : dp[(r-1)*mxn+c-1]) {
		if (v) {
			cnt += amt;
			cnt %= mod;
		}
	}
	
	cnt = (mod+nck(r+c-2,c-1)-cnt)%mod;
	cout<<cnt;
}

Compilation message (stderr)

mobitel.cpp: In function 'int main()':
mobitel.cpp:50:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |     for (auto [v,amt] : dp[i*mxn+j]) {
      |               ^
mobitel.cpp:56:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |     for (auto [v,amt] : dp[i*mxn+j]) {
      |               ^
mobitel.cpp:66:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |  for (auto [v,amt] : dp[(r-1)*mxn+c-1]) {
      |            ^

• Subtask 1: 91 / 130