oj.uz

Submission #100470

# Submission time Handle Problem Language Result Execution time Memory
100470 2019-03-11T13:37:35 Z markotee Mobitel (COCI19_mobitel) C++17
130 / 130
 1205 ms 2948 KB 
#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.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 2940 KB Output is correct
2 Correct 76 ms 2944 KB Output is correct
3 Correct 94 ms 1152 KB Output is correct
4 Correct 98 ms 1152 KB Output is correct
5 Correct 126 ms 1152 KB Output is correct
6 Correct 109 ms 1192 KB Output is correct
7 Correct 57 ms 940 KB Output is correct
8 Correct 623 ms 2304 KB Output is correct
9 Correct 1205 ms 2936 KB Output is correct
10 Correct 1168 ms 2948 KB Output is correct