oj.uz

Submission #708583

# Submission time Handle Problem Language Result Execution time Memory
708583 2023-03-12T04:01:14 Z Matjaz Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 164556 KB 
#include<vector>
#include<iostream>
#include <stdlib.h> 
#include <algorithm>
#include <stack>
#include <string.h>

using namespace std;


long long dp[1<<20][20];
int N;
vector<int> a;

int ones(int x, int base){
	int ans = 0;

	while (x > 0){
		if (x % base == 1) ans++;
		x /= base;
	}
	return ans;
}

bool works(int a, int b){
	return ones(a, 2) == ones(b,2) || ones(a, 3) == ones(b, 3);
}

long long ways(int S, int last){
	if (dp[S][last] != -1) return dp[S][last];
	if (S == (1<<N) - 1) return 1;

	long long ans = 0;


	for (int i=0;i<N;i++){
		if ((S & (1<<i)) != 0) continue;
		if (works(a[last], a[i])) ans += ways(S + (1<<i), i);
	}

	return dp[S][last] = ans;
}

int main(){
	memset(dp, -1, sizeof(dp));

	cin >> N;
	a.assign(N, 0);
	for (int i=0;i<N;i++)
		cin >> a[i];


	long long total = 0;
	for (int i=0;i<N;i++) 
		total += ways(1<<i, i);

	cout << total << endl;

	return 0;
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 164360 KB Output is correct
2 Correct 63 ms 164428 KB Output is correct
3 Correct 59 ms 164440 KB Output is correct
4 Correct 62 ms 164384 KB Output is correct
5 Correct 61 ms 164428 KB Output is correct
6 Correct 62 ms 164376 KB Output is correct
7 Correct 59 ms 164428 KB Output is correct
8 Correct 69 ms 164432 KB Output is correct
9 Correct 58 ms 164392 KB Output is correct
10 Correct 61 ms 164380 KB Output is correct
11 Correct 114 ms 164444 KB Output is correct
12 Correct 100 ms 164444 KB Output is correct
13 Correct 310 ms 164384 KB Output is correct
14 Correct 1534 ms 164440 KB Output is correct
15 Correct 1608 ms 164444 KB Output is correct
16 Correct 1340 ms 164556 KB Output is correct
17 Correct 1722 ms 164496 KB Output is correct
18 Correct 1390 ms 164440 KB Output is correct
19 Execution timed out 3070 ms 164416 KB Time limit exceeded
20 Halted 0 ms 0 KB -