oj.uz

Submission #369327

# Submission time Handle Problem Language Result Execution time Memory
369327 2021-02-21T10:10:08 Z Sparky_09 Mobitel (COCI19_mobitel) C++17
130 / 130
 4317 ms 5796 KB 
#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

int rd() {
	int result = 0;
	char ch;
	ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	result = ch-'0';
	while (true) {
		ch = getchar();
		if (ch < '0' || ch > '9') break;
		result = result*10 + (ch - '0');
	}
	return result;
}

template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int N = 300 + 3;
const int K = 2010;
int n, m, v, dp[2][N][K], a[N][N];
int cnt;
int val[1000010], id[1000010];
inline int q(int a, int b){ 
    return int(ceil(1.0 * a / b));
}

void init(){
    for(int i = 1; i <= v; i++){
        int tmp = q(v, i);

        if(id[tmp])
            continue;

        val[id[tmp] = cnt++] = tmp;
    }
}

const int mod = int(1e9) + 7;
void add(int &a, int &b) {
    a = (a + b) % mod;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
    cin >> n >> m >> v;
    init();

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            cin >> a[i][j];

    dp[0][1][id[v]] = 1;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++)
            for(int k = 0; k < cnt; k++)
                dp[i & 1][j][k] = 0;

        for(int j = 1; j <= m; j++)
            for(int k = 0; k < cnt; k++){
                int from = id[q(val[k], a[i][j])];
                add(dp[i & 1][j][from], dp[(i - 1) & 1][j][k]);

                if(j > 1)
                    add(dp[i & 1][j][from], dp[i & 1][j - 1][k]);
            }
    }

    int r = dp[n & 1][m][id[1]];
    cout << r << '\n';
}

Compilation message

mobitel.cpp: In function 'void usaco(std::string)':
mobitel.cpp:30:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   30 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:31:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   31 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3180 KB Output is correct
2 Correct 79 ms 3180 KB Output is correct
3 Correct 454 ms 2412 KB Output is correct
4 Correct 479 ms 2284 KB Output is correct
5 Correct 485 ms 2432 KB Output is correct
6 Correct 486 ms 2412 KB Output is correct
7 Correct 238 ms 1900 KB Output is correct
8 Correct 2329 ms 4460 KB Output is correct
9 Correct 4247 ms 5712 KB Output is correct
10 Correct 4317 ms 5796 KB Output is correct