Submission #100470

#	Time	Username	Problem	Language	Result	Execution time	Memory
100470		markotee	Mobitel (COCI19_mobitel)	C++17	130 / 130	1205 ms	2948 KiB

mobitel

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
int add(int &x, int y) { return (x += y) < MOD ? x : x -= MOD; }
int sub(int &x, int y) { return (x -= y) >= 00 ? x : x += MOD; }

int dp[305][2][1005];

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  int r, s, n;
  cin >> r >> s >> n;
  dp[1][0][1] = 1;
  int root = ceil(sqrt(n));
  for (int i = 1; i <= r; ++i) {
    for (int i = 1; i <= s; ++i) {
      int num;
      cin >> num;
      int tmp[2][1005] = {};
      for (int j = 1; j < root; ++j) {
        int prod = min(j * num, n);
        if (prod < root) {
          add(tmp[0][prod], dp[i][0][j]);
          add(tmp[0][prod], dp[i - 1][0][j]);
        } else {
          add(tmp[1][(n - 1) / prod + 1], dp[i][0][j]);
          add(tmp[1][(n - 1) / prod + 1], dp[i - 1][0][j]);
        }
      }
      for (int j = 1; j <= root; ++j) {
        add(tmp[1][(j - 1) / num + 1], dp[i][1][j]);
        add(tmp[1][(j - 1) / num + 1], dp[i - 1][1][j]);
      }
      memcpy(dp[i], tmp, sizeof tmp);
    }
  }
  cout << dp[s][1][1] << '\n';
}

• Subtask 1: 130 / 130