Submission #102226

#	Time	Username	Problem	Language	Result	Execution time	Memory
102226		IvanC	Mobitel (COCI19_mobitel)	C++17	130 / 130	2398 ms	11016 KiB

mobitel

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> ii;
 
const int MAXN = 302;
const int MOD = 1e9 + 7;
 
vector<ii> paths[2][MAXN];
int matriz[MAXN][MAXN],R,S,N, current_x;
ll tot;
 
ll fast_expo(ll x, ll y){
	if(y == 0) return 1;
	if(y % 2 == 0){
		ll temp = fast_expo(x, y/2);
		return (temp*temp) % MOD;
	}
	else{
		return (x*fast_expo(x, y - 1)) % MOD;
	}
}
 
ll mod_inv(ll x){
	return fast_expo(x, MOD - 2);
}
 
ll fatorial(int n){
 
	ll ans = 1;
	for(int i = 2;i<=n;i++){
		ans = (ans * i) % MOD;
	}
 
	return ans;
 
}
 
ll binomial(int n, int k){
 
	ll ans = (fatorial(n) * mod_inv(fatorial(k)) ) % MOD;
	ans = (ans *  mod_inv(fatorial(n - k))) % MOD;
 
	return ans;
 
}
 
void in_place_merge(int x, int y, int factor){
 
	int ptr[2], a[2], b[2], sz[2];
	ptr[0] = ptr[1] = 0;
	a[0] = x, a[1] = x ^ 1;
	b[0] = y - 1, b[1] = y; 
	sz[0] = paths[a[0]][b[0]].size(), sz[1] = paths[a[1]][b[1]].size();
 
	while(ptr[0] < sz[0] || ptr[1] < sz[1]){
 
		ii element = ii(-1, -1);
 
		if(ptr[0] == sz[0]){
			if(paths[a[1]][b[1]][ptr[1]].first < factor){
				ptr[1] = sz[1];
				continue;
			}
			element = paths[a[1]][b[1]][ptr[1]];
			ptr[1]++;
		}
		else if(ptr[1] == sz[1]){
			if(paths[a[0]][b[0]][ptr[0]].first < factor){
				ptr[0] = sz[0];
				continue;
			}
			element = paths[a[0]][b[0]][ptr[0]];
			ptr[0]++;
		}
		else if(paths[a[0]][b[0]][ptr[0]] >= paths[a[1]][b[1]][ptr[1]]){
			if(paths[a[0]][b[0]][ptr[0]].first < factor){
				ptr[0] = sz[0];
				continue;
			}
			element = paths[a[0]][b[0]][ptr[0]];
			ptr[0]++;
		}
		else{
			if(paths[a[1]][b[1]][ptr[1]].first < factor){
				ptr[1] = sz[1];
				continue;
			}
			element = paths[a[1]][b[1]][ptr[1]];
			ptr[1]++;
		}
 
		if(paths[x][y].empty() || paths[x][y].back().first != element.first){
			paths[x][y].push_back(element);
		}
		else{
			paths[x][y].back().second = (paths[x][y].back().second + element.second) % MOD;
		}
 
	}
 
	for(int i = 0;i < paths[x][y].size();i++){
		paths[x][y][i].first /= factor;
	}
 
}
 
int main(){
 
	scanf("%d %d %d", &R, &S, &N);
	N--;
 
	for(int i = 1;i<=R;i++){
		for(int j = 1;j<=S;j++){
			scanf("%d",&matriz[i][j]);
		}
	}
 
	paths[current_x][1].push_back(ii(N / matriz[1][1], 1));
	for(int i = 2;i<=S;i++){
		in_place_merge(current_x, i, matriz[1][i]);
	}
 
	for(int i = 2;i <= R;i++){
 
		current_x ^= 1;
		for(int j = 1;j<=S;j++) paths[current_x][j].clear();
 
		for(int j = 1;j<=S;j++){
			in_place_merge(current_x, j, matriz[i][j]);
		}
 
	}
 
	ll ans = binomial(R + S - 2, S - 1);
	for(ii davez : paths[current_x][S]){
		ans = ans - davez.second;
		ans %= MOD;
	}
 
	if(ans < 0) ans += MOD;
	printf("%lld\n",ans);
 
	return 0;
 
}

Compilation message (stderr)

mobitel.cpp: In function 'void in_place_merge(int, int, int)':
mobitel.cpp:103:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i < paths[x][y].size();i++){
                ~~^~~~~~~~~~~~~~~~~~~~
mobitel.cpp: In function 'int main()':
mobitel.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &R, &S, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:116:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&matriz[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 130 / 130