oj.uz

Submission #100508

# Submission time Handle Problem Language Result Execution time Memory
100508 2019-03-11T20:33:29 Z Milki Mobitel (COCI19_mobitel) C++14
130 / 130
 800 ms 5760 KB 
#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

typedef long long ll;
typedef pair<int, int> point;

const int mod = 1e9 + 7, MAXN = 305, MAXSQ = 1005;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

int r, s, n;
int a[MAXN][MAXN], dp1[MAXN][MAXSQ], dp2[MAXN][MAXSQ];
int tmp1[MAXN][MAXSQ], tmp2[MAXN][MAXSQ];

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  cin >> r >> s >> n;
  REP(i, r) REP(j, s) cin >> a[i + 1][j + 1];
  const int SQRT = (sqrt(n) + 1);

  FOR(i, 1, r + 1){
    memset(tmp1, 0, sizeof(tmp1)); memset(tmp2, 0, sizeof(tmp2));

    if(i == 1){
      if(a[1][1] < SQRT)
        tmp1[1][ a[1][1] ] = 1;
      else
        tmp2[1][ (n - 1) / a[1][1] ] = 1;
    }

    FOR(j, 1, s + 1) FOR(k, 0, SQRT + 1){
      int pr = min(a[i][j] * k, n);
      if(pr < SQRT){
        tmp1[j][pr] = add(tmp1[j][pr], dp1[j][k]);
        tmp1[j][pr] = add(tmp1[j][pr], tmp1[j - 1][k]);
        //if(i == 2 && j == 1) TRACE(tmp1[j][k]);
      }
      else{
        int pos = (n - 1) / pr;
        tmp2[j][pos] = add(tmp2[j][pos], dp1[j][k]);
        tmp2[j][pos] = add(tmp2[j][pos], tmp1[j - 1][k]);
        //if(tmp2[j][pos]) TRACE(i), TRACE(j), TRACE(k), TRACE(pos);
      }
      //if(tmp1[j][pr] > 0) TRACE(tmp1[j][pr]), TRACE(i), TRACE(j), TRACE(k), TRACE(a[i][j] * k);

      int pos = k / a[i][j];
      tmp2[j][pos] = add(tmp2[j][pos], dp2[j][k]);
      tmp2[j][pos] = add(tmp2[j][pos], tmp2[j - 1][k]);
      //if(tmp2[j][pos] > 0) TRACE(i), TRACE(j), TRACE(k), TRACE(pos), TRACE(a[i][j]);
    }
    memcpy(dp1, tmp1, sizeof(tmp1));
    memcpy(dp2, tmp2, sizeof(tmp2));
  }
  cout << dp2[s][0];
}

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5760 KB Output is correct
2 Correct 125 ms 5716 KB Output is correct
3 Correct 118 ms 5344 KB Output is correct
4 Correct 116 ms 5368 KB Output is correct
5 Correct 137 ms 5344 KB Output is correct
6 Correct 131 ms 5304 KB Output is correct
7 Correct 62 ms 5248 KB Output is correct
8 Correct 431 ms 5536 KB Output is correct
9 Correct 769 ms 5752 KB Output is correct
10 Correct 800 ms 5752 KB Output is correct