oj.uz

Submission #203369

# Submission time Handle Problem Language Result Execution time Memory
203369 2020-02-20T11:33:32 Z vanic Zapina (COCI20_zapina) C++14
55 / 110
 1000 ms 83108 KB 
#include <cstdio>

typedef long long ll;

const int maxn=355, mod=1e9+7, Log=30;

int fact[maxn];
int dp[maxn][maxn][2];

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	else if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}


inline int mul(int a, int b){
	return (ll)a*b%mod;
}


int pot(int a, int b){
	int sol=1;
	for(int i=0; i<Log; i++){
		if((1<<i)&b){
			sol=mul(sol, a);
		}
		a=mul(a, a);
	}
	return sol;
}

inline int dijel(int a, int b){
	return mul(a, pot(b, mod-2));
}

int n;
int povrh[maxn][maxn][maxn];

void precompute(){
	fact[0]=1;
	for(int i=1; i<maxn; i++){
		fact[i]=mul(fact[i-1], i);
	}
	for(int i=0; i<=n; i++){
		for(int j=0; j<=i; j++){
			povrh[n-j][i-j][n-i]=dijel(fact[n-j], mul(fact[i-j], fact[n-i]));
		}
	}
}

int main(){
	scanf("%d", &n);
	precompute();
	dp[0][0][0]=1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			for(int l=0; l<=j; l++){
				if(j-l==i){
/*						if(i==1 && j==1 && l==0 && k==1){
						cout << "da" << endl;
						cout << dp[i-1][l][k-1] << endl;
						cout <<  fact[j-l] <<  " " << fact[n-j] << endl;
					}*/
					dp[i][j][1]=sum(dp[i][j][1], mul(sum(dp[i-1][l][0], dp[i-1][l][1]), povrh[n-l][j-l][n-j]));
				}
				else{
					dp[i][j][0]=sum(dp[i][j][0], mul(dp[i-1][l][0], povrh[n-l][j-l][n-j]));
					dp[i][j][1]=sum(dp[i][j][1], mul(dp[i-1][l][1], povrh[n-l][j-l][n-j]));
				}
			}
		}
	}
	int sol=0;
//	cout << dp[2][2][1] << " " << dp[2][2][2] << endl;
	for(int j=1; j<30; j++){
//		cout << dp[n][n][j] << " ";
		sol=sum(sol, dp[n][n][j]);
	}
//	cout << endl;
	printf("%d\n", sol);
	return 0;
}

Compilation message

zapina.cpp: In function 'int main()':
zapina.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
zapina.cpp:82:10: warning: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
   sol=sum(sol, dp[n][n][j]);
       ~~~^~~~~~~~~~~~~~~~~~
zapina.cpp:80:16: note: within this loop
  for(int j=1; j<30; j++){
               ~^~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 632 KB Output is correct
14 Correct 5 ms 636 KB Output is correct
15 Correct 5 ms 760 KB Output is correct
16 Correct 5 ms 760 KB Output is correct

Subtask #3
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Correct 5 ms 632 KB Output is correct
13 Correct 5 ms 632 KB Output is correct
14 Correct 5 ms 636 KB Output is correct
15 Correct 5 ms 760 KB Output is correct
16 Correct 5 ms 760 KB Output is correct
17 Correct 347 ms 54520 KB Output is correct
18 Correct 8 ms 2680 KB Output is correct
19 Correct 74 ms 20088 KB Output is correct
20 Correct 5 ms 888 KB Output is correct
21 Correct 568 ms 65888 KB Output is correct
22 Correct 64 ms 15864 KB Output is correct
23 Correct 9 ms 3448 KB Output is correct
24 Correct 88 ms 24056 KB Output is correct
25 Correct 61 ms 18680 KB Output is correct
26 Correct 115 ms 29304 KB Output is correct
27 Execution timed out 1096 ms 83108 KB Time limit exceeded
28 Halted 0 ms 0 KB -