Submission #335389

#TimeUsernameProblemLanguageResultExecution timeMemory
335389dooweyMobitel (COCI19_mobitel)C++14
13 / 130
237 ms65540 KiB
#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[N][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[1][1][idx[(k-1)/A[1][1]]]=1; int f; for(int i = 1; i <= n; i ++ ){ for(int j = 1; j <= m ; j ++ ){ for(int c = 0; c < rel.size(); c ++ ){ if(dp[i][j][c] == 0) continue; if(i + 1 <= n){ f = rel[c]/A[i+1][j]; add(dp[i+1][j][idx[f]],dp[i][j][c]); } if(j + 1 <= m){ f = rel[c]/A[i][j+1]; add(dp[i][j+1][idx[f]],dp[i][j][c]); } } } } cout << dp[n][m][0] << "\n"; return 0; }

Compilation message (stderr)

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:58:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for(int c = 0; c < rel.size(); c ++ ){
      |                            ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...