oj.uz

Submission #100269

# Submission time Handle Problem Language Result Execution time Memory
100269 2019-03-10T07:20:59 Z ami Mobitel (COCI19_mobitel) C++14
130 / 130
 2275 ms 10588 KB 
#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.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3840 KB Output is correct
2 Correct 27 ms 3840 KB Output is correct
3 Correct 81 ms 5888 KB Output is correct
4 Correct 81 ms 6400 KB Output is correct
5 Correct 209 ms 6392 KB Output is correct
6 Correct 151 ms 6356 KB Output is correct
7 Correct 69 ms 5392 KB Output is correct
8 Correct 1128 ms 8768 KB Output is correct
9 Correct 2275 ms 10488 KB Output is correct
10 Correct 2160 ms 10588 KB Output is correct