Submission #114019

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
114019	2019-05-29T14:58:58 Z	shayan_p	Tents (JOI18_tents)	C++14	100 / 100	165 ms	35676 KB

tents

// High above the clouds there is a rainbow...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn=3010,mod=1e9+7;
const ll inf=1e18;

int dp[maxn][maxn];

int C(int n){
    if(n<2) return 0;
    return (1ll*n*(n-1) /2) %mod;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;cin>>n>>m;
    dp[0][0]=1;
    for(int j=1;j<=m;j++){
	dp[0][j]=1;
	dp[1][j]=(C(j) + 4*j + 1) %mod;
    }
    for(int i=1;i<=n;i++){
	dp[i][0]=1;
	dp[i][1]=(C(i) + 4*i + 1) %mod;
    }
    for(int i=2;i<=n;i++){
	for(int j=2;j<=m;j++){
	    dp[i][j]=(1ll*C(j)*dp[i-1][j-2] + 1ll*(i-1)*(j)*dp[i-2][j-1] + 4ll*j*dp[i-1][j-1] + 1ll*dp[i-1][j] )%mod;
	}
    }
    int ans=dp[n][m]-1;
    if(ans<0) ans+=mod;
    return cout<<ans<<endl,0;
}
// Deathly mistakes:
//  * Read the problem curfully.
//  * Check maxn.
//  * Overflows.

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	7 ms	512 KB	Output is correct
4	Correct	3 ms	1152 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	1280 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	3 ms	1408 KB	Output is correct
9	Correct	2 ms	896 KB	Output is correct
10	Correct	3 ms	1664 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	4 ms	1920 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	7 ms	512 KB	Output is correct
4	Correct	3 ms	1152 KB	Output is correct
5	Correct	2 ms	640 KB	Output is correct
6	Correct	3 ms	1280 KB	Output is correct
7	Correct	3 ms	768 KB	Output is correct
8	Correct	3 ms	1408 KB	Output is correct
9	Correct	2 ms	896 KB	Output is correct
10	Correct	3 ms	1664 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	4 ms	1920 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	9 ms	9600 KB	Output is correct
15	Correct	42 ms	33020 KB	Output is correct
16	Correct	5 ms	2688 KB	Output is correct
17	Correct	12 ms	7936 KB	Output is correct
18	Correct	15 ms	11008 KB	Output is correct
19	Correct	49 ms	34728 KB	Output is correct
20	Correct	38 ms	29176 KB	Output is correct
21	Correct	25 ms	19840 KB	Output is correct
22	Correct	28 ms	22264 KB	Output is correct
23	Correct	22 ms	19712 KB	Output is correct
24	Correct	51 ms	35676 KB	Output is correct
25	Correct	44 ms	30808 KB	Output is correct
26	Correct	48 ms	33528 KB	Output is correct
27	Correct	165 ms	34736 KB	Output is correct