oj.uz

Submission #101952

# Submission time Handle Problem Language Result Execution time Memory
101952 2019-03-21T07:38:40 Z Rudy420 Tents (JOI18_tents) C++17
100 / 100
 238 ms 71132 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

int n,m;

ll mod=1e9+7,dp[3005][3005];

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

    cin >> n >> m;
    for(int j=0;j<=m;j++) dp[0][j]=1;
    for(int j=0;j<=n;j++) dp[j][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1 && j>1) dp[i][j]=dp[i][j-1]+dp[i-1][j-1]*i*4+dp[i-2][j-1]*i*(i-1)/2+dp[i-1][j-2]*i*(j-1);
            else if(i>1)  dp[i][j]=dp[i][j-1]+dp[i-1][j-1]*i*4+dp[i-2][j-1]*i*(i-1)/2;
            else if(j>1) dp[i][j]=dp[i][j-1]+dp[i-1][j-1]*i*4+dp[i-1][j-2]*i*(j-1);
            else dp[i][j]=dp[i][j-1]+dp[i-1][j-1]*i*4;
            dp[i][j]%=mod;
        }
    }
    cout << (dp[n][m]-1+mod)%mod;
}

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 5 ms 1792 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 6 ms 2304 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 1152 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 4 ms 1408 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 1408 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 5 ms 1792 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 6 ms 2304 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 27 ms 9728 KB Output is correct
15 Correct 153 ms 55260 KB Output is correct
16 Correct 13 ms 4224 KB Output is correct
17 Correct 40 ms 12828 KB Output is correct
18 Correct 46 ms 17116 KB Output is correct
19 Correct 172 ms 63096 KB Output is correct
20 Correct 136 ms 50960 KB Output is correct
21 Correct 94 ms 33912 KB Output is correct
22 Correct 96 ms 35604 KB Output is correct
23 Correct 59 ms 27128 KB Output is correct
24 Correct 238 ms 71132 KB Output is correct
25 Correct 167 ms 61228 KB Output is correct
26 Correct 200 ms 66680 KB Output is correct
27 Correct 220 ms 69016 KB Output is correct