oj.uz

Submission #102525

# Submission time Handle Problem Language Result Execution time Memory
102525 2019-03-25T17:09:13 Z Nnandi Mobitel (COCI19_mobitel) C++14
0 / 130
 218 ms 66560 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxrs = 305;
const int maxme = 1005;
const ll mod = 1000000007LL;
ll dpkis[maxrs][maxrs][maxme];
ll dpnagy[maxrs][maxrs][maxme];
ll tab[maxrs][maxrs];
int r, s;
ll n, m;

int main()
{
    cin>>r>>s>>n;
    m = (ll)sqrt(n);

    for(int i=0;i<r;i++) {
        for(int j=0;j<s;j++) {
            cin>>tab[i][j];
        }
    }
    for(int c=1;c<=min(tab[0][0],m);c++) {
        dpkis[0][0][c] = 1LL;
    }

    for(int i=0;i<r;i++) {
        for(int j=0;j<s;j++) {
            for(int c=1;c<=m;c++) {
                int req = (int)max(1LL,(c + tab[i][j] - 1) / tab[i][j]);
                dpkis[i][j][c] += (i > 0 ? dpkis[i-1][j][req] : 0LL);
                dpkis[i][j][c] += (j > 0 ? dpkis[i][j-1][req] : 0LL);
                dpkis[i][j][c] %= mod;
            }
        }
    }
    for(int i=0;i<r;i++) {
        for(int j=0;j<s;j++) {
            for(int c=1;c<=m;c++) {
                if(i == 0 && j == 0 && n <= c) dpnagy[i][j][c] = 1LL;
                if(c * tab[i][j] > m) {
                    int prereq = (n+c-1) / c;
                    int req = (prereq + tab[i][j] - 1) / tab[i][j];
                    dpnagy[i][j][c] += (i > 0 ? dpkis[i-1][j][req] : 0LL);
                    dpnagy[i][j][c] += (j > 0 ? dpkis[i][j-1][req] : 0LL);
                    dpnagy[i][j][c] %= mod;
                }
                else {
                    int req = c * tab[i][j];
                    dpnagy[i][j][c] += (i > 0 ? dpnagy[i-1][j][req] : 0LL);
                    dpnagy[i][j][c] += (j > 0 ? dpnagy[i][j-1][req] : 0LL);
                    dpnagy[i][j][c] %= mod;
                }
            }
        }
    }
    cout<<dpnagy[r-1][s-1][1]<<endl;
    return 0;
}

Subtask #1
0 / 130.0

# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 95 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 201 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 204 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 202 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 218 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 190 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 212 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 212 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 210 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)