Submission #334958

#	Time	Username	Problem	Language	Result	Execution time	Memory
334958		ronnith	Mobitel (COCI19_mobitel)	C++14	26 / 130	364 ms	65540 KiB

mobitel

#include <bits/stdc++.h>
#define trav(a, b) for(auto a : b)
#define mk make_pair
#define f first
#define s second
#define vi vector<int>
#define pb push_back
#define _  << ' ' << 
typedef long long ll;
using namespace std;
const ll modF = 1e9 + 7;

ll ceil(ll a, ll b){
	ll res = a / b;
	if(a % b != 0)res ++;
	return res;
}

int main(){
	// ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	ll n, m, k;
	scanf("%lld%lld%lld", &n, &m, &k);
	ll a[n][m];
	for(int i = 0;i < n;i ++){
		for(int j = 0;j < m;j ++){
			scanf("%lld", &a[i][j]);
		}
	}
	vector<vector<vector<ll>>> dp(2, vector<vector<ll>>(m, vector<ll>(k + 1)));
	int crr = 0;
	int prev = 1;
	auto val = [&](int i, int j, int it){
		if(it == 0)return 0LL;
		if(it == 1)return dp[i][j][it];
		else return (dp[i][j][it] - dp[i][j][it - 1] + modF) % modF;
	};
	auto v = [&](int i, int j, int it){
		if(it == 0)return 0LL;
		return dp[i][j][it];
	};
	for(int i = 0;i < n;i ++){
		for(int j = 0;j < m;j ++){
			dp[crr][j][k] = 0;
			for(int it = 1;it < k; it ++){
				// cerr << i _ j _ it << '\n';
				dp[crr][j][it] = 0;
				if(i == 0 and j == 0){
					if(a[i][j] == it){
						dp[crr][j][it] = 1;
					}
				} else {
					if(it % a[i][j] == 0){
						int rem = it / a[i][j];
						if(i != 0)dp[crr][j][it] = (dp[crr][j][it] + val(prev, j, rem)) % modF;
						if(j != 0)dp[crr][j][it] = (dp[crr][j][it] + val(crr, j - 1, rem)) % modF;
					}
				}
				if(it != 1)
					dp[crr][j][it] = (dp[crr][j][it] + dp[crr][j][it - 1]) % modF;
				// cerr << dp[crr][j][it] << ' ';
			}
			// cerr << "yes";
			ll req = ceil(k, a[i][j]);
			// cerr << req _ a[i][j] << " ";
			if(i != 0)
			dp[crr][j][k] = (dp[crr][j][k] + (v(prev,j,k) - v(prev,j, req - 1) + modF) % modF) % modF; 
			if(j != 0)
			dp[crr][j][k] = (dp[crr][j][k] + (v(crr,j - 1,k) - v(crr,j - 1, req - 1) + modF) % modF) % modF;
			if(k != 1)
				dp[crr][j][k] = (dp[crr][j][k] + dp[crr][j][k - 1]) % modF; 
			// cerr << dp[crr][j][k] << ' ';
		}
		// cerr << '\n';
		crr = 1 - crr;
		prev = 1 - prev;
	}
	ll ans = val(prev,m - 1,k);
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

mobitel.cpp: In function 'int main()':
mobitel.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%lld%lld%lld", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   26 |    scanf("%lld", &a[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 26 / 130