Submission #100269

#	Time	Username	Problem	Language	Result	Execution time	Memory
100269		ami	Mobitel (COCI19_mobitel)	C++14	130 / 130	2275 ms	10588 KiB

mobitel

#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using ll = long long;

const int MD=int(1e9)+7;
void madd(int &x,int y) {
	x+=y;
	if (x>=MD) x-=MD;
}

int const MAXR=330;
int const MAXN=1100000;
int const MAXK=2200;
int R,C,N;
ll a[MAXR][MAXR];
int ord[MAXN];
ll smallest[MAXN];
int f[2][MAXR][MAXK];

inline int get_ord(ll x) {
	if (x<N) return ord[x]; else return ord[N];
}

int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cout<<fixed<<setprecision(10);

	cin>>R>>C>>N;
	rep(i,0,R) rep(j,0,C) cin>>a[i][j];

	rep(i,1,N+1) {
		ord[i]=ord[i-1];
		if (i==1 || ((N+i-1)/i != (N+i-2)/(i-1))) {
			ord[i]++;
			smallest[ord[i]]=i;
		}
	}

	int K=ord[N];
	rep(i,0,C) rep(j,1,K+1) f[0][i][j]=0;
	f[0][0][get_ord(a[0][0])]=1;

	rep(i,0,R) {
		int cur=i%2;
		int nxt=!cur;

		rep(j,0,C) rep(k,1,K+1) f[nxt][j][k]=0;

		rep(j,0,C) rep(k,1,K+1) if (f[cur][j][k]) {
			if (j+1<C) {
				int nk=get_ord(smallest[k]*a[i][j+1]);
				madd(f[cur][j+1][nk],f[cur][j][k]);
			}
			if (i+1<R) {
				int nk=get_ord(smallest[k]*a[i+1][j]);
				madd(f[nxt][j][nk],f[cur][j][k]);
			}
		}
	}

	cout<<f[(R-1)%2][C-1][K]<<"\n";
}

• Subtask 1: 130 / 130