oj.uz

Submission #708589

# Submission time Handle Problem Language Result Execution time Memory
708589 2023-03-12T04:05:24 Z Matjaz Beautiful row (IZhO12_beauty) C++14
100 / 100
 2705 ms 164528 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 onesdp[20][4];

int ones(int x, int base){
	if (onesdp[x][base] != -1) return onesdp[x][base];
	int ans = 0;

	int tmp = a[x];

	while (tmp > 0){
		if (tmp % base == 1) ans++;
		tmp /= base;
	}
	return onesdp[x][base] = 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(last, i)) ans += ways(S + (1<<i), i);
	}

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

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

	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
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 164332 KB Output is correct
2 Correct 64 ms 164352 KB Output is correct
3 Correct 66 ms 164388 KB Output is correct
4 Correct 62 ms 164428 KB Output is correct
5 Correct 60 ms 164344 KB Output is correct
6 Correct 62 ms 164428 KB Output is correct
7 Correct 63 ms 164356 KB Output is correct
8 Correct 63 ms 164428 KB Output is correct
9 Correct 62 ms 164320 KB Output is correct
10 Correct 62 ms 164444 KB Output is correct
11 Correct 72 ms 164412 KB Output is correct
12 Correct 69 ms 164328 KB Output is correct
13 Correct 127 ms 164432 KB Output is correct
14 Correct 440 ms 164528 KB Output is correct
15 Correct 505 ms 164432 KB Output is correct
16 Correct 371 ms 164464 KB Output is correct
17 Correct 456 ms 164436 KB Output is correct
18 Correct 315 ms 164436 KB Output is correct
19 Correct 2550 ms 164440 KB Output is correct
20 Correct 2705 ms 164444 KB Output is correct