Submission #219732

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219732	2020-04-06T07:20:43 Z	dorijanlendvaj	Tents (JOI18_tents)	C++14	100 / 100	255 ms	35704 KB

tents

//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

const int N=3010;
int n,m,dp[N][N];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)[phone]);
	cin>>n>>m;
	for (int i=0;i<=max(n,m);++i) dp[i][0]=dp[0][i]=1;
	for (int i=1;i<=n;++i) for (int j=1;j<=m;++j)
	{
		dp[i][j]=mult(j*4,dp[i-1][j-1]);
		dp[i][j]=add(dp[i][j],dp[i-1][j]);
		if (i>1) dp[i][j]=add(dp[i][j],mult(j*(i-1),dp[i-2][j-1]));
		if (j>1) dp[i][j]=add(dp[i][j],mult(j*(j-1)/2,dp[i-1][j-2]));
	}
	cout<<sub(dp[n][m],1);
}

Subtask #1

48.0 / 48.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	1024 KB	Output is correct
3	Correct	5 ms	640 KB	Output is correct
4	Correct	5 ms	1152 KB	Output is correct
5	Correct	6 ms	1408 KB	Output is correct
6	Correct	6 ms	1408 KB	Output is correct
7	Correct	5 ms	1280 KB	Output is correct
8	Correct	5 ms	1408 KB	Output is correct
9	Correct	5 ms	896 KB	Output is correct
10	Correct	6 ms	1664 KB	Output is correct
11	Correct	5 ms	1536 KB	Output is correct
12	Correct	7 ms	1920 KB	Output is correct

Subtask #2

52.0 / 52.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	1024 KB	Output is correct
3	Correct	5 ms	640 KB	Output is correct
4	Correct	5 ms	1152 KB	Output is correct
5	Correct	6 ms	1408 KB	Output is correct
6	Correct	6 ms	1408 KB	Output is correct
7	Correct	5 ms	1280 KB	Output is correct
8	Correct	5 ms	1408 KB	Output is correct
9	Correct	5 ms	896 KB	Output is correct
10	Correct	6 ms	1664 KB	Output is correct
11	Correct	5 ms	1536 KB	Output is correct
12	Correct	7 ms	1920 KB	Output is correct
13	Correct	8 ms	7808 KB	Output is correct
14	Correct	9 ms	9600 KB	Output is correct
15	Correct	161 ms	32864 KB	Output is correct
16	Correct	19 ms	8064 KB	Output is correct
17	Correct	40 ms	12408 KB	Output is correct
18	Correct	47 ms	11768 KB	Output is correct
19	Correct	184 ms	34680 KB	Output is correct
20	Correct	146 ms	29176 KB	Output is correct
21	Correct	99 ms	21496 KB	Output is correct
22	Correct	97 ms	22264 KB	Output is correct
23	Correct	59 ms	19704 KB	Output is correct
24	Correct	255 ms	35704 KB	Output is correct
25	Correct	183 ms	30840 KB	Output is correct
26	Correct	212 ms	33544 KB	Output is correct
27	Correct	240 ms	34936 KB	Output is correct