oj.uz

Submission #536549

# Submission time Handle Problem Language Result Execution time Memory
536549 2022-03-13T13:52:50 Z errorgorn Mobitel (COCI19_mobitel) C++17
130 / 130
 2015 ms 5932 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

int n,m,k;
vector<int> val;
int id[1000005];
int memo[2][305][2005];
int grid[305][305];

int cdiv(int i,int j){ //shit ceiling
	return (i-1)/j+1;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m>>k;
	rep(x,1,n+1) rep(y,1,m+1) cin>>grid[x][y];
	
	rep(x,1,k+1){
		int temp=cdiv(k,x);
		if (val.empty() || val.back()!=temp){
			id[temp]=sz(val);
			val.push_back(temp);
		}
	}
	
	int a=0,b=1;
	memo[a][1][0]=1;
	rep(x,1,n+1){
		rep(y,1,m+1){
			rep(z,0,sz(val)){
				int temp=id[cdiv(val[z],grid[x][y])];
				memo[b][y][temp]=((ll)memo[b][y][temp]+memo[a][y][z]+memo[b][y-1][z])%MOD;
				//cout<<x<<" "<<y<<" "<<val[temp]<<" "<<memo[b][y][temp]<<endl;
			}
		}
		
		swap(a,b);
		memset(memo[b],0,sizeof(memo[b]));
	}
	
	cout<<memo[a][m][id[1]]<<endl;
}

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 5668 KB Output is correct
2 Correct 61 ms 5588 KB Output is correct
3 Correct 236 ms 5492 KB Output is correct
4 Correct 249 ms 5580 KB Output is correct
5 Correct 228 ms 5520 KB Output is correct
6 Correct 239 ms 5460 KB Output is correct
7 Correct 118 ms 5460 KB Output is correct
8 Correct 1107 ms 5736 KB Output is correct
9 Correct 2015 ms 5932 KB Output is correct
10 Correct 1977 ms 5928 KB Output is correct