oj.uz

Submission #335390

# Submission time Handle Problem Language Result Execution time Memory
335390 2020-12-12T10:50:30 Z doowey Mobitel (COCI19_mobitel) C++14
130 / 130
 3357 ms 9836 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 310;
const int L = 2100;
const int MAX = (int)1e6 + 10;
const int MOD = (int)1e9 + 7;
int A[N][N];
int idx[MAX];
vector<int> cur;
int dp[2][N][L];

void add(int &a, int b){
    a += b;
    if(a >= MOD)
        a -= MOD;
}

int main(){
    fastIO;
    int n,m,k;
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1 ; j <= m; j ++ ){
            cin >> A[i][j];
        }
    }
    vector<int> rel;
    rel.push_back(0);
    int vl;
    for(int i = k-1; i >= 1 ; i -- ){
        vl = (k-1)/i;
        if(vl != rel.back())
            rel.push_back((k-1)/i);
    }
    for(int i = 0 ; i <= k ; i ++ ){
        idx[i] = -1;
    }
    for(int i = 0; i < rel.size(); i ++ ){
        idx[rel[i]] = i;
    }
    for(int i = 0 ; i <= k ; i ++ ){
        if(idx[i]==-1)idx[i]=idx[i-1];
    }
    dp[0][1][idx[(k-1)/A[1][1]]]=1;
    int f;
    int bit=0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 1; j <= m ; j ++ ){
            for(int q = 0; q < rel.size(); q ++ ){
                dp[(bit^1)][j][q]=0;
            }
        }
        for(int j = 1; j <= m ; j ++ ){
            for(int c = 0; c < rel.size(); c ++ ){
                if(dp[bit][j][c] == 0) continue;
                if(i + 1 <= n){
                    f = rel[c]/A[i+1][j];
                    add(dp[(bit^1)][j][idx[f]],dp[bit][j][c]);
                }
                if(j + 1 <= m){
                    f = rel[c]/A[i][j+1];
                    add(dp[bit][j+1][idx[f]],dp[bit][j][c]);
                }
            }
        }
        bit ^= 1;
    }
    cout << dp[(bit^1)][m][0] << "\n";
    return 0;
}

Compilation message

mobitel.cpp: In function 'int main()':
mobitel.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < rel.size(); i ++ ){
      |                    ~~^~~~~~~~~~~~
mobitel.cpp:59:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |             for(int q = 0; q < rel.size(); q ++ ){
      |                            ~~^~~~~~~~~~~~
mobitel.cpp:64:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int c = 0; c < rel.size(); c ++ ){
      |                            ~~^~~~~~~~~~~~

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3436 KB Output is correct
2 Correct 57 ms 3436 KB Output is correct
3 Correct 127 ms 5612 KB Output is correct
4 Correct 138 ms 6252 KB Output is correct
5 Correct 273 ms 6136 KB Output is correct
6 Correct 251 ms 6124 KB Output is correct
7 Correct 115 ms 5228 KB Output is correct
8 Correct 1681 ms 8300 KB Output is correct
9 Correct 3296 ms 9836 KB Output is correct
10 Correct 3357 ms 9836 KB Output is correct