oj.uz

Submission #833425

# Submission time Handle Problem Language Result Execution time Memory
833425 2023-08-22T05:32:18 Z rahulverma Beautiful row (IZhO12_beauty) Java 11
0 / 100
 3000 ms 224688 KB 
import java.util.*;
import java.io.*;

public class beauty {
    static long[] a = new long[100];
    static long[] b = new long[100];
    static long[][] dp = new long[1 << 20][23];
    static int n;

    static long rec(long mask, int last) {
        if (mask == (pow(n) - 1)) return 1;

        if (last != -1 && dp[(int) mask][last] != -1) return dp[(int) mask][last];
        long an = 0;
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) == 0) {
                if (last == -1 || a[(int) last] == a[i] || b[(int) last] == b[i]) {
                    an += rec(mask | pow(i), i);
                }
            }
        }
        if(last != -1)dp[(int) mask][last] = an;
        return an;
    }

    public static void main(String[] args) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int i;
        long ans = 0;

        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (i = 0; i < n; i++) {
            long p = Integer.parseInt(st.nextToken());
            a[i] = Long.bitCount(p);
            long p1 = p;
            while (p1 > 0) {
                if (p1 % 3 == 1) b[i]++;
                p1 /= 3;
            }
        }
        for (i = 0; i < pow(20); i++) {
            Arrays.fill(dp[i], -1);
        }
        ans += rec(0, -1);
        PrintWriter pw = new PrintWriter(System.out);
        pw.println(ans);
        pw.close();
    }
    public static long pow(int i) {
    	long ans = 1;
    	while(i > 0) {
    		ans *= 2;
    		i--;
    	}
    	return ans;
    }
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 363 ms 222460 KB Output is correct
2 Correct 337 ms 222244 KB Output is correct
3 Correct 366 ms 222456 KB Output is correct
4 Correct 357 ms 222484 KB Output is correct
5 Correct 347 ms 222392 KB Output is correct
6 Correct 346 ms 224144 KB Output is correct
7 Correct 399 ms 224092 KB Output is correct
8 Correct 386 ms 223968 KB Output is correct
9 Correct 396 ms 224072 KB Output is correct
10 Correct 397 ms 224080 KB Output is correct
11 Correct 400 ms 223904 KB Output is correct
12 Correct 429 ms 224688 KB Output is correct
13 Correct 467 ms 224332 KB Output is correct
14 Correct 899 ms 223920 KB Output is correct
15 Correct 857 ms 223868 KB Output is correct
16 Correct 756 ms 224504 KB Output is correct
17 Correct 840 ms 224248 KB Output is correct
18 Correct 670 ms 224468 KB Output is correct
19 Execution timed out 3032 ms 223776 KB Time limit exceeded
20 Halted 0 ms 0 KB -