oj.uz

Submission #1034081

# Submission time Handle Problem Language Result Execution time Memory
1034081 2024-07-25T09:37:01 Z anHiep Tents (JOI18_tents) C++14
48 / 100
 2000 ms 313700 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vi vector<int>
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
#define ld long double
#define all(x) (x).begin(), (x).end()
#define iii tuple<int, int, int>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 1e7;
int tc, tt = 1;

ll h, w;
ll fac[N + 5], inv[N + 5];
ll g[N + 5];
ll f[N + 5];

ll powmod(ll a, ll b) {
    ll ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}

void prep() {
    fac[0] = 1;
    for(int i=1; i<=N; i++) fac[i] = fac[i - 1] * i % mod;
    inv[N] = powmod(fac[N], mod - 2);
    for(ll i=N-1; i>=0; i--)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}

ll C(ll n, ll k) {
    ll ans = fac[n];
    ans = ans * inv[k] % mod;
    ans = ans * inv[n - k] % mod;
    return ans;
}

void solve() {
    prep();
    f[0] = 1;
    for(int i=1; i<=N; i++) f[i] = f[i - 1] * 4 % mod;
    g[0] = 1;
    for(int i=2; i<=N; i+=2) g[i] = g[i - 2] * C(i, 2) % mod; 
    cin>>h>>w;
    ll ans = 0;
    for(int i=0; i<=min(h, w/2); i++) {
        ll cal = C(h, i) * C(w, i * 2) % mod;
        cal = cal * g[i * 2] % mod;
        for(int j=0; j<=min(w - 2 * i, (h - i)/2); j++) {
            ll cal2 = C(w - 2 * i, j) * C(h - i, j * 2) % mod;
            cal2 = cal2 * g[j * 2] % mod;
            ll cnt = min((w - 2 * i - j), (h - i - j * 2));
            ll fical = cal * cal2 % mod;
            ll sum = 0;
            for(int k=0; k<=cnt; k++) {
                if(i == 0 && j == 0 && k == 0) continue;
                ll v = f[k];
                v = v * C(w - 2*i - j, k) % mod;
                v = v * C(h - i - j * 2, k) % mod;
                v = v * fac[k] % mod;
                sum = (sum + v) % mod;
            }
            fical = fical * sum % mod;
            ans = (ans + fical) % mod;
        }
    }
    cout<<ans;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    for(tc=1; tc<=tt; tc++) solve();
    cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
    return 0;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 313428 KB Output is correct
2 Correct 279 ms 313424 KB Output is correct
3 Correct 255 ms 313428 KB Output is correct
4 Correct 255 ms 313428 KB Output is correct
5 Correct 255 ms 313360 KB Output is correct
6 Correct 255 ms 313428 KB Output is correct
7 Correct 255 ms 313424 KB Output is correct
8 Correct 257 ms 313348 KB Output is correct
9 Correct 280 ms 313520 KB Output is correct
10 Correct 259 ms 313504 KB Output is correct
11 Correct 253 ms 313320 KB Output is correct
12 Correct 287 ms 313424 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 313428 KB Output is correct
2 Correct 279 ms 313424 KB Output is correct
3 Correct 255 ms 313428 KB Output is correct
4 Correct 255 ms 313428 KB Output is correct
5 Correct 255 ms 313360 KB Output is correct
6 Correct 255 ms 313428 KB Output is correct
7 Correct 255 ms 313424 KB Output is correct
8 Correct 257 ms 313348 KB Output is correct
9 Correct 280 ms 313520 KB Output is correct
10 Correct 259 ms 313504 KB Output is correct
11 Correct 253 ms 313320 KB Output is correct
12 Correct 287 ms 313424 KB Output is correct
13 Correct 257 ms 313512 KB Output is correct
14 Correct 266 ms 313424 KB Output is correct
15 Execution timed out 2090 ms 313700 KB Time limit exceeded
16 Halted 0 ms 0 KB -