# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
369325 | Sparky_09 | Mobitel (COCI19_mobitel) | C++17 | 6073 ms | 7916 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
int rd() {
int result = 0;
char ch;
ch = getchar();
while(ch < '0' || ch > '9') ch = getchar();
result = ch-'0';
while (true) {
ch = getchar();
if (ch < '0' || ch > '9') break;
result = result*10 + (ch - '0');
}
return result;
}
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
void usaco(string s){
freopen((s+".in").c_str(), "r", stdin);
freopen((s+".out").c_str(), "w", stdout);
}
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
const int N = 300 + 3;
const int K = 3010;
int n, m, v, dp[2][N][K], a[N][N];
int cnt;
unordered_map<int, int, custom_hash> val, id;
inline int q(int a, int b){
return int(ceil(1.0 * a / b));
}
void init(){
for(int i = 1; i <= v; i++){
int tmp = q(v, i);
if (id.count(tmp))
continue;
val[id[tmp] = cnt++] = tmp;
}
}
const int mod = int(1e9) + 7;
void add(int &a, int &b) {
a = (a + b) % mod;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
freopen("input.txt", "r", stdin);
#endif
cin >> n >> m >> v;
init();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> a[i][j];
dp[0][1][id[v]] = 1;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++)
for(int k = 0; k < cnt; k++)
dp[i & 1][j][k] = 0;
for(int j = 1; j <= m; j++)
for(int k = 0; k < cnt; k++){
int from = id[q(val[k], a[i][j])];
add(dp[i & 1][j][from], dp[(i - 1) & 1][j][k]);
if(j > 1)
add(dp[i & 1][j][from], dp[i & 1][j - 1][k]);
}
}
int r = dp[n & 1][m][id[1]];
cout << r << endl;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |