oj.uz

Submission #319475

# Submission time Handle Problem Language Result Execution time Memory
319475 2020-11-05T11:00:52 Z ronnith Zapina (COCI20_zapina) C++14
55 / 110
 1000 ms 652 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#warning Check Integer OverFlow
#define ll long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define trav(a,b) for(auto a:b)
#define sz(a) a.size()
#define maxs(a,b) if(b>a)a=b
#define mins(a,b) if(b<a)a=b
#ifdef LOCAL 
	#define dbg(x) cerr<<"["<<#x<<":"<<x<<"] "
	#define dbg2(a,b) dbg(a);dbg(b)
	#define dbg3(a,b,c) dbg2(a,b);dbg(c)
	#define dln cerr << ln
#else
	#define dbg(x) 0
	#define dbg2(a,b) 0
	#define dbg3(a,b,c) 0
	#define dln 0
#endif
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (((a)/(__gcd(a,b))) * b)
#define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define v vector
#define p pair
#define pii p<int,int>
#define pb push_back
#define mk make_pair
#define f first
#define s second
#define ln "\n"
typedef long double ld;
using namespace std;
using namespace __gnu_pbds;
ll modF=1e9+7;

template<class T> using iset = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;

/*OUTPUT

*/

v<ll> fac(355,1);

void g(int a,int b,int* x,int* y){
	if(a == 0){
		*x = 0;
		*y = 1;
	}
	else{
		int x1,y1;
		g(b % a,a,&x1,&y1);
		*x = y1 - (b / a) * x1;
		*y = x1;
	}
}

ll modInverse(int a){
	int x,y;
	g(a,modF,&x,&y);
	while(x < 0)x += modF;
	return x % modF;
}

ll nCr(ll n,ll r){
	return (fac[n] * modInverse((fac[n - r] * fac[r]) % modF)) % modF;
}

void solve(){
	int n;
	cin >> n;
	ll dp1[n][n + 1];
	ll dp2[n][n + 1];
	for(ll i = 0;i < n;i ++){
		for(ll j = 0;j <= n;j ++){
			if(i == 0){
				dp2[i][j] = 1;
				if(j == i + 1)
					dp1[i][j] = 1;
				else
					dp1[i][j] = 0;
			}
			else{
				dp1[i][j] = dp2[i][j] = 0;
				for(int k = 0;k <= j;k ++){
					dp2[i][j] = (dp2[i][j] + (nCr(j,k) * dp2[i - 1][j - k]) % modF) % modF;
				}
				if(j >= i + 1){
					dp1[i][j] = (nCr(j,i + 1) * dp2[i - 1][j - i - 1]) % modF;
				}
				for(int k = 0;k <= j;k ++){
					if(k == i + 1)continue;
					dp1[i][j] = (dp1[i][j] + (nCr(j,k) * dp1[i - 1][j - k])) % modF;
				}
			}
		}
	}
	cout << dp1[n - 1][n] << ln;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	rep(i,1,351){
		fac[i] = (fac[i - 1] * i) % modF;
	}
	// cin >> t;
	while(t --){
		solve();
	}
}

Compilation message

zapina.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
    4 | #warning Check Integer OverFlow
      |  ^~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 396 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 396 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Execution timed out 1049 ms 652 KB Time limit exceeded
18 Halted 0 ms 0 KB -