Submission #536549

#	Time	Username	Problem	Language	Result	Execution time	Memory
536549		errorgorn	Mobitel (COCI19_mobitel)	C++17	130 / 130	2015 ms	5932 KiB

mobitel

//雪花飄飄北風嘯嘯
//天地一片蒼茫

#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 / 130