Submission #102172

#	Time	Username	Problem	Language	Result	Execution time	Memory
102172		IvanC	Mobitel (COCI19_mobitel)	C++17	91 / 130	3127 ms	66560 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],dp[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 second_factor){

	int max_value = N/second_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 > max_value){
				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 > max_value){
				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 > max_value){
				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 > max_value){
				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 solve(int x,int y){

	if(dp[x][y] != 0) return dp[x][y];

	if(x == R && y == S) return matriz[x][y];

	ll cand;

	if(x + 1 <= R && y + 1 <= S){
		cand = 1LL*matriz[x][y]*min(solve(x+1,y), solve(x, y + 1));
	}
	else if(x + 1 <= R){
		cand = 1LL*matriz[x][y]*solve(x+1,y);
	}
	else{
		cand = 1LL*matriz[x][y]*solve(x,y+1);
	}

	if(cand <= N){
		return dp[x][y] = cand;
	}
	else{
		return dp[x][y] = N+1;
	}

}

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]);
		}
	}

	if(matriz[1][1] <= N) paths[current_x][1].push_back(ii(matriz[1][1], 1));
	for(int i = 2;i<=S;i++){
		in_place_merge(current_x, i, matriz[1][i], solve(1, i));
	}

	for(int i = 2;i <= R;i++){

		current_x ^= 1;
		for(int j = 1;j<=S;j++){
			paths[current_x][j].clear();
			paths[current_x][j].shrink_to_fit();
		}

		for(int j = 1;j<=S;j++){
			in_place_merge(current_x, j, matriz[i][j], solve(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, int)':
mobitel.cpp:106: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:141: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:146: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: 91 / 130