oj.uz

Submission #331288

# Submission time Handle Problem Language Result Execution time Memory
331288 2020-11-28T00:34:48 Z AnythingWithJ A Huge Tower (CEOI10_tower) Java 11
15 / 100
 1000 ms 198700 KB 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class tower {
    static TreeSet<Integer> visited;
    static int MOD = 1000000009;
    static List<List<Integer>> graph;
    static int N, D;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer s = new StringTokenizer(br.readLine());
        N = Integer.parseInt(s.nextToken());
        D = Integer.parseInt(s.nextToken());
        int [] towers = new int[N+1];
        s = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            towers[i] = Integer.parseInt(s.nextToken());
        }
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (j==i) continue;
                if (towers[i] <= towers[j]+D) {
                    graph.get(i).add(j);
                }
            }
        }
        visited = new TreeSet<>();
        long res = 0;
        for (int i = 1; i <= N; i++) {
            visited.clear();
            res += dfs (i);
            res %= MOD;
        }
        System.out.println(res);
    }
    static long dfs (int currNode) {
        if (visited.contains(currNode)) return 0;
        visited.add(currNode);
        //System.out.println(currNode+" start");
        //System.out.println(visited);
        if (visited.size() == N) {
            visited.remove(currNode);
            return 1;
        }
        long currRes = 0;
        for (int adj : graph.get(currNode)) {
            if (!visited.contains(adj)) currRes += dfs(adj);
            currRes %= MOD;
        }
        visited.remove(currNode);
        //System.out.println(currNode+" end");
        //System.out.println(visited);
        return currRes;
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8936 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 13040 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 15012 KB Time limit exceeded

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 15676 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 14836 KB Time limit exceeded

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 15052 KB Time limit exceeded

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1099 ms 14956 KB Time limit exceeded

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 14804 KB Time limit exceeded

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1049 ms 15564 KB Time limit exceeded

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 14984 KB Time limit exceeded

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 14752 KB Time limit exceeded

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 14880 KB Time limit exceeded

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 14868 KB Time limit exceeded

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 15448 KB Time limit exceeded

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 34916 KB Time limit exceeded

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 91036 KB Time limit exceeded

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 198016 KB Time limit exceeded

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 180916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1101 ms 149844 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1075 ms 198700 KB Time limit exceeded
2 Halted 0 ms 0 KB -