oj.uz

Submission #101331

# Submission time Handle Problem Language Result Execution time Memory
101331 2019-03-18T13:25:36 Z Rudy420 Tents (JOI18_tents) C++17
48 / 100
 2000 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005

ll fact[6005],inv[6005],mod=1e9+7,ans,pw[6005],ip[6005];

ll pwr(ll a, ll p){
    if(!p) return 1;
    ll t=pwr(a,p/2);
    t*=t; t%=mod;
    if(p%2) t*=a, t%=mod;
    return t;
}

int n,m;


int32_t main(){
    /*seed_seq seq{
        (uint64_t) chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(),
        (uint64_t) __builtin_ia32_rdtsc(),
        (uint64_t) (uintptr_t) make_unique<char>().get()
    };
    mt19937 rng(seq);*/
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
#ifdef LOCAL_DEFINE
    ifstream cin("input.in");
#endif

    fact[0]=inv[0]=pw[0]=ip[0]=1;
    for(int i=1;i<=6000;i++){
        fact[i]=fact[i-1]*i%mod;
        inv[i]=pwr(fact[i],mod-2);
        pw[i]=pw[i-1]*2%mod;
        ip[i]=pwr(pw[i],mod-2);
    }

    cin >> n >> m;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=n-2*i && j<=m-i;j++){
            for(int k=0;k<=n-2*i-j && k<=m-i-2*j;k++){
                if(i+j+k){
                    ans+=fact[n]*fact[m]%mod*inv[n-2*i-j-k]%mod*inv[m-i-2*j-k]%mod*inv[i]%mod*inv[j]%mod*inv[k]%mod*ip[i]%mod*ip[j]%mod*pw[2*k]%mod;
                    ans%=mod;
                }
            }
        }
    }
    cout << ans;

}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 13 ms 512 KB Output is correct
3 Correct 13 ms 512 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 23 ms 512 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 16 ms 512 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 51 ms 512 KB Output is correct
11 Correct 13 ms 512 KB Output is correct
12 Correct 268 ms 596 KB Output is correct

Subtask #2
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 512 KB Output is correct
2 Correct 13 ms 512 KB Output is correct
3 Correct 13 ms 512 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 17 ms 512 KB Output is correct
6 Correct 23 ms 512 KB Output is correct
7 Correct 24 ms 512 KB Output is correct
8 Correct 16 ms 512 KB Output is correct
9 Correct 13 ms 512 KB Output is correct
10 Correct 51 ms 512 KB Output is correct
11 Correct 13 ms 512 KB Output is correct
12 Correct 268 ms 596 KB Output is correct
13 Correct 14 ms 512 KB Output is correct
14 Correct 14 ms 512 KB Output is correct
15 Execution timed out 2045 ms 512 KB Time limit exceeded
16 Halted 0 ms 0 KB -