Submission #342713

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
342713	2021-01-02T16:37:01 Z	bigDuck	Tents (JOI18_tents)	C++14	100 / 100	462 ms	71060 KB

tents

#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
#define int ll

int t, n, m, k, a[300010], q, l, r;

int dp[3010][3010];
int mod=((int)1e9)+7;


int32_t main(){
INIT
cin>>n>>m;
dp[0][0]=1;
for(int i=1; i<=n; i++){
    for(int j=1; j<=m; j++){
        if(j>=2){
            dp[i][j]=(dp[i][j]+((max(dp[i-1][j-2], 1ll)*(j*(j-1)/2))%mod)%mod)%mod;
        }
        dp[i][j]=(dp[i][j]+(max(dp[i-1][j-1], 1ll)*4*(j))%mod)%mod;
        if(i>=2){
            dp[i][j]=(dp[i][j]+(max(dp[i-2][j-1], 1ll)*(j)*(i-1) )%mod)%mod;
        }
        dp[i][j]=(dp[i][j]+max(dp[i-1][j], 1ll) ) %mod;
        //cout<<dp[i][j]<<" ";
    }
    //cout<<"\n";
}
cout<<(dp[n][m]-1);

return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	2 ms	748 KB	Output is correct
6	Correct	2 ms	1388 KB	Output is correct
7	Correct	2 ms	876 KB	Output is correct
8	Correct	2 ms	1516 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	3 ms	1772 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	5 ms	2284 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	492 KB	Output is correct
4	Correct	1 ms	1132 KB	Output is correct
5	Correct	2 ms	748 KB	Output is correct
6	Correct	2 ms	1388 KB	Output is correct
7	Correct	2 ms	876 KB	Output is correct
8	Correct	2 ms	1516 KB	Output is correct
9	Correct	1 ms	876 KB	Output is correct
10	Correct	3 ms	1772 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	5 ms	2284 KB	Output is correct
13	Correct	1 ms	364 KB	Output is correct
14	Correct	7 ms	9708 KB	Output is correct
15	Correct	295 ms	55224 KB	Output is correct
16	Correct	19 ms	4096 KB	Output is correct
17	Correct	68 ms	12908 KB	Output is correct
18	Correct	81 ms	17132 KB	Output is correct
19	Correct	335 ms	62956 KB	Output is correct
20	Correct	268 ms	50924 KB	Output is correct
21	Correct	178 ms	33936 KB	Output is correct
22	Correct	178 ms	35436 KB	Output is correct
23	Correct	100 ms	27116 KB	Output is correct
24	Correct	462 ms	71060 KB	Output is correct
25	Correct	345 ms	61340 KB	Output is correct
26	Correct	396 ms	66716 KB	Output is correct
27	Correct	442 ms	69116 KB	Output is correct