Submission #45815

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
45815	2018-04-16T08:00:08 Z	mraron	Tents (JOI18_tents)	C++14	100 / 100	246 ms	71648 KB

tents

//Noszály Áron 10o Debreceni Fazekas Mihály Gimnázium

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define pb push_back
#define xx first
#define yy second
#define sz(x) (int)(x).size()
#define gc getchar
#define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mp make_pair

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const double PI=acos(-1);

template<typename T> T getint() {
	T val=0;
	char c;
	
	bool neg=false;
	while((c=gc()) && !(c>='0' && c<='9')) {
		neg|=c=='-';
	}

	do {
		val=(val*10)+c-'0';
	} while((c=gc()) && (c>='0' && c<='9'));

	return val*(neg?-1:1);
}

const ll mod=1e9+7;

ll dp[3001][3001];

ll calc(int i, int j) {
	if(i==0 || j==0) return 1;
	if(dp[i][j]!=-1) return dp[i][j];
	ll ans=0;
	if(i>1) ans=(ans+calc(i-2, j-1)*i*(i-1)/2)%mod;
	ans=(ans+4*calc(i-1,j-1)*i)%mod;
	if(j>1) ans=(ans+calc(i-1,j-2)*i*(j-1))%mod;
	ans=(ans+calc(i,j-1))%mod;
	
	return dp[i][j]=ans;
}


int main() {
	IO;
	memset(dp, -1, sizeof dp);
	int a,b;
	cin>>a>>b;
	cout<<(calc(a,b)-1+mod)%mod<<"\n";
	
	return 0;
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	70776 KB	Output is correct
2	Correct	53 ms	71028 KB	Output is correct
3	Correct	53 ms	71028 KB	Output is correct
4	Correct	53 ms	71028 KB	Output is correct
5	Correct	54 ms	71028 KB	Output is correct
6	Correct	53 ms	71028 KB	Output is correct
7	Correct	53 ms	71092 KB	Output is correct
8	Correct	53 ms	71092 KB	Output is correct
9	Correct	53 ms	71164 KB	Output is correct
10	Correct	54 ms	71164 KB	Output is correct
11	Correct	56 ms	71212 KB	Output is correct
12	Correct	61 ms	71212 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	70776 KB	Output is correct
2	Correct	53 ms	71028 KB	Output is correct
3	Correct	53 ms	71028 KB	Output is correct
4	Correct	53 ms	71028 KB	Output is correct
5	Correct	54 ms	71028 KB	Output is correct
6	Correct	53 ms	71028 KB	Output is correct
7	Correct	53 ms	71092 KB	Output is correct
8	Correct	53 ms	71092 KB	Output is correct
9	Correct	53 ms	71164 KB	Output is correct
10	Correct	54 ms	71164 KB	Output is correct
11	Correct	56 ms	71212 KB	Output is correct
12	Correct	61 ms	71212 KB	Output is correct
13	Correct	58 ms	71280 KB	Output is correct
14	Correct	66 ms	71280 KB	Output is correct
15	Correct	181 ms	71416 KB	Output is correct
16	Correct	87 ms	71416 KB	Output is correct
17	Correct	120 ms	71452 KB	Output is correct
18	Correct	96 ms	71452 KB	Output is correct
19	Correct	236 ms	71496 KB	Output is correct
20	Correct	195 ms	71540 KB	Output is correct
21	Correct	137 ms	71544 KB	Output is correct
22	Correct	122 ms	71544 KB	Output is correct
23	Correct	67 ms	71544 KB	Output is correct
24	Correct	245 ms	71544 KB	Output is correct
25	Correct	199 ms	71544 KB	Output is correct
26	Correct	221 ms	71648 KB	Output is correct
27	Correct	246 ms	71648 KB	Output is correct