oj.uz

Submission #456275

# Submission time Handle Problem Language Result Execution time Memory
456275 2021-08-06T10:15:32 Z Dakto Tents (JOI18_tents) C++17
100 / 100
 1801 ms 35756 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include <ext/pb_ds/detail/standard_policies.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DEBUGMODE 1
#ifdef ONLINE_JUDGE
#define DEBUGMODE 0
#endif

#define cerr if(DEBUGMODE) cerr
#define DEBUG(a) if(DEBUGMODE) cout<<(a)<<endl
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define EACH(i,c) for(auto (i):c)
#define endl '\n'
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define LLM LONG_LONG_MAX
#define gcd __gcd
#define pb push_back
#define pm make_pair
#define MANY_TESTS ll ntests; cin>>ntests; for(ll test=1; test<=ntests; test++) 
#define contains(a,b) ((a).find(b)!=(a).end())
#define INF 1e16
#define NINF -1e16
#define cinv(n,v) ll n; cin>>n; vl v(n); cin>>v;
#define fact(f,n) vl f={0}; for(ll i=0; i<n; i++) f.push_back(f[i]*(i+1));
#define codejamout(s) cout<<"Case #"<<test<<": "<<s<<"\n";
#define LOG(x) cerr<<"Line "<<__LINE__<<":"<<#x<<" = "<<x<<endl;


typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll,ll>> vpll;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll MOD=1e9+7;

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "(" << par.first << ";" << par.second << ")"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }

template<typename T>
pair<T, ll> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return {*it, it - v.begin()};}
template<typename T>
pair<T, ll> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return {*it, it - v.begin()};}        
template<class T>
bool remin(T& a, const T& b){return (b<a?a=b,1:0);}
template<class T>
bool remax(T& a, const T& b){return (a<b?a=b,1:0);}

ll getbit(ll number, ll index){return (number & (1<<index))<<index;}


template <int MOD=1'000'000'007>
struct ModInt {
  int value;
  static const int MOD_value = MOD;

  ModInt(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;}
  ModInt(long long a, long long b) : value(0){ *this += a; *this /= b;}

  ModInt& operator+=(ModInt const& b) {value += b.value; if (value >= MOD) value -= MOD; return *this;}
  ModInt& operator-=(ModInt const& b) {value -= b.value; if (value < 0) value += MOD;return *this;}
  ModInt& operator*=(ModInt const& b) {value = (long long)value * b.value % MOD;return *this;}

  friend ModInt mexp(ModInt a, long long e) {
    ModInt res = 1; while (e) { if (e&1) res *= a; a *= a; e >>= 1; }
    return res;
  }
  friend ModInt inverse(ModInt a) { return mexp(a, MOD - 2); }

  ModInt& operator/=(ModInt const& b) { return *this *= inverse(b); }
  friend ModInt operator+(ModInt a, ModInt const b) { return a += b; }
  friend ModInt operator-(ModInt a, ModInt const b) { return a -= b; }
  friend ModInt operator-(ModInt const a) { return 0 - a; }
  friend ModInt operator*(ModInt a, ModInt const b) { return a *= b; }
  friend ModInt operator/(ModInt a, ModInt const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, ModInt const& a) {return os << a.value;}
  friend bool operator==(ModInt const& a, ModInt const& b) {return a.value == b.value;}
  friend bool operator!=(ModInt const& a, ModInt const& b) {return a.value != b.value;}
};


int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    ll h,w;
    cin>>h>>w;

    vector<vector<ModInt<>>> dp(w+5,vector<ModInt<>>(h+5,0));

    dp[0][0]=1;

    REP(i,w+1){
        REP(j,h+1){
            dp[i+1][j]+=dp[i][j];
            dp[i+1][j+2]+=dp[i][j]*(h-j)*(h-j-1)/2;
            dp[i+1][j+1]+=dp[i][j]*(h-j)*4;
            dp[i+2][j+1]+=dp[i][j]*(h-j)*(i+1);
        }
    }

    ll res=0;
    REPR(i,1,h+1){
        res+=dp[w][i].value;
    }

    cout<<res%MOD<<endl;

    
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 4 ms 360 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 10 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 19 ms 688 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 4 ms 360 KB Output is correct
6 Correct 5 ms 332 KB Output is correct
7 Correct 5 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 10 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 19 ms 688 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 1145 ms 22360 KB Output is correct
16 Correct 72 ms 1740 KB Output is correct
17 Correct 256 ms 5292 KB Output is correct
18 Correct 310 ms 6452 KB Output is correct
19 Correct 1332 ms 26004 KB Output is correct
20 Correct 1052 ms 20856 KB Output is correct
21 Correct 694 ms 13876 KB Output is correct
22 Correct 687 ms 13664 KB Output is correct
23 Correct 382 ms 7724 KB Output is correct
24 Correct 1801 ms 35756 KB Output is correct
25 Correct 1338 ms 26620 KB Output is correct
26 Correct 1530 ms 30468 KB Output is correct
27 Correct 1741 ms 34372 KB Output is correct