oj.uz

Submission #362289

# Submission time Handle Problem Language Result Execution time Memory
362289 2021-02-02T14:15:06 Z n00bie_1004 Tents (JOI18_tents) C++14
100 / 100
 469 ms 73732 KB 
#include <bits/stdc++.h>
 
typedef long long int ll;
typedef long double ld;
typedef unsigned long long int ull;
typedef long int li;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define test ll t; cin >> t; while(t--)
const long long int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0}; 
const long long int cons = 3005, ncr_cons = 100005;
const long long int MOD = 1000000007; // const long long int MOD = 998244353; 
const long long int const_INT_MAX = 1000000000000000000, const_INT_MIN = -1 * 1000000000000000000;
using namespace std;
bool sortinrev(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.first > b.first);}
bool sortbysec(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.second < b.second);}
bool sortbysecinrev(const pair<ll,ll> &a, const pair<ll,ll> &b){return (a.second > b.second);}
ll gcd(ll x, ll y){return (ll)(__gcd(x, y));}   
ll lcm(ll x, ll y){return (ll)((x * y) / gcd(x, y));}
ll mod_expo(ll x, ll y, ll p){  
    ll res = 1;
    if((x + p) % p == 0){
        return res = 0;
    }
    x = (x + p) % p;
    while (y > 0){   
        if(y & 1) res = (res*x + p) % p; 
        y = y>>1; x = (x*x + p) % p;  
    }  
    return res;    
}
void usaco(string str = ""){    
    fastio; 
    if(str.size()){
        freopen((str + ".in").c_str(), "r", stdin); 
        freopen((str + ".out").c_str(), "w", stdout);
    }   
}
ll invnum[ncr_cons], invfac[ncr_cons], fac[ncr_cons]; 
void pre_ncr(){ // add pre_ncr() in main 
    invnum[0] = invnum[1] = invfac[0] = invfac[1] = fac[0] = 1; 
    for(ll i=2;i<ncr_cons;i++){
        invnum[i] = ((invnum[MOD % i] * (MOD - (MOD / i)) + MOD) % MOD);
    }
    for(ll i=2;i<ncr_cons;i++){
        invfac[i] = ((invnum[i] * invfac[i-1] + MOD) % MOD);
    }
    for(ll i=1;i<ncr_cons;i++){
        fac[i] = ((fac[i-1] * i + MOD) % MOD); 
    }
}
ll ncr(ll n, ll r){
    ll ans = ((fac[n] * invfac[r] + MOD) % MOD) * ((invfac[n-r] + MOD) % MOD); 
    ans += MOD; ans %= MOD; return ans;
}
ll dp[cons][cons];
ll solve(ll h, ll w){
    if(min(h, w) < 0) return 0; 
    if(dp[h][w] != -1) return dp[h][w]; 
    
    ll var = 0; 
    var += (ll)(((solve(h-1, w-1) * h + MOD) % MOD * 4 + MOD) % MOD); var %= MOD; 
    var += (ll)(solve(h, w-1)); var %= MOD;
    var += (ll)(((solve(h-2, w-1) + MOD) % MOD) * ((ncr(h, 2) + MOD) % MOD)); var %= MOD; 
    var += (ll)(((solve(h-1, w-2) + MOD) % MOD) * ((h * (w-1) + MOD) % MOD)); var %= MOD;

    return dp[h][w] = var; 
} 
int main(){ 
    usaco(); pre_ncr();
    for(ll i=0;i<cons;i++){
        for(ll j=0;j<cons;j++){
            if(!(min(i, j))) dp[i][j] = 1; 
            else dp[i][j] = -1; 
        }
    }
    ll h, w; cin >> h >> w; 
    ll var = solve(h, w); var--; var += MOD; var %= MOD; cout << var << "\n";
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

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

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 73324 KB Output is correct
2 Correct 59 ms 73324 KB Output is correct
3 Correct 50 ms 73452 KB Output is correct
4 Correct 51 ms 73356 KB Output is correct
5 Correct 51 ms 73452 KB Output is correct
6 Correct 53 ms 73324 KB Output is correct
7 Correct 52 ms 73452 KB Output is correct
8 Correct 51 ms 73324 KB Output is correct
9 Correct 51 ms 73324 KB Output is correct
10 Correct 52 ms 73324 KB Output is correct
11 Correct 52 ms 73452 KB Output is correct
12 Correct 54 ms 73452 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 73324 KB Output is correct
2 Correct 59 ms 73324 KB Output is correct
3 Correct 50 ms 73452 KB Output is correct
4 Correct 51 ms 73356 KB Output is correct
5 Correct 51 ms 73452 KB Output is correct
6 Correct 53 ms 73324 KB Output is correct
7 Correct 52 ms 73452 KB Output is correct
8 Correct 51 ms 73324 KB Output is correct
9 Correct 51 ms 73324 KB Output is correct
10 Correct 52 ms 73324 KB Output is correct
11 Correct 52 ms 73452 KB Output is correct
12 Correct 54 ms 73452 KB Output is correct
13 Correct 51 ms 73580 KB Output is correct
14 Correct 52 ms 73452 KB Output is correct
15 Correct 295 ms 73732 KB Output is correct
16 Correct 70 ms 73452 KB Output is correct
17 Correct 104 ms 73580 KB Output is correct
18 Correct 114 ms 73580 KB Output is correct
19 Correct 342 ms 73708 KB Output is correct
20 Correct 277 ms 73708 KB Output is correct
21 Correct 200 ms 73580 KB Output is correct
22 Correct 186 ms 73556 KB Output is correct
23 Correct 72 ms 73472 KB Output is correct
24 Correct 467 ms 73708 KB Output is correct
25 Correct 355 ms 73580 KB Output is correct
26 Correct 404 ms 73708 KB Output is correct
27 Correct 469 ms 73708 KB Output is correct