oj.uz

Submission #263630

# Submission time Handle Problem Language Result Execution time Memory
263630 2020-08-13T22:53:12 Z ijxjdjd Boat (APIO16_boat) Java 11
0 / 100
 166 ms 15156 KB 

import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;

public class boat {
    static long[][] choose = new long[501][501];
    static long[] inverse = new long[505];
    public static long inverse(long a, long mod) {
        long[] inv = extended_gcd(a, mod);
        if (inv[0] != 1) {
            return 0;
        }
        else {
            return (inv[1] + 2*mod)%mod;
        }
    }
    public static long[] extended_gcd(long a, long b) {
        //three numbers, first is gcd, second is x, third is y
        if (a == 0) {
            return new long[]{b, 0, 1};
        }
        long[] next = extended_gcd(b%a, a);
        long tempX = next[1];
        next[1] = next[2] - (b/a) * next[1];
        next[2] = tempX;
        return next;
    }

    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int N = in.nextInt();
        int[][] intervals = new int[N][2];
        HashSet<Integer> points = new HashSet<>();
        for (int i = 0; i <= 500; i++) {
            choose[i][0] = 1;
            for (int j = 1; j <= i; j++) {
                choose[i][j] = (choose[i-1][j] + choose[i-1][j-1])%MOD;
            }
        }
        for (int i = 1; i < inverse.length; i++) {
            inverse[i] = inverse(i, MOD);
        }
        for (int i = 0; i < N; i++) {
            intervals[i][0] = in.nextInt();
            intervals[i][1] = in.nextInt();
            points.add(intervals[i][0]);
            points.add(intervals[i][1]+1);
        }
        ArrayList<Integer> pSort = new ArrayList<>(points);
        ArrayList<ArrayList<Integer>> items = new ArrayList<>();
        for (int i = 0; i < pSort.size(); i++) {
            items.add(new ArrayList<>());
        }
        Collections.sort(pSort);
        for (int i = 0; i < N; i++) {
            boolean flag = false;
            for (int j = 0; j < pSort.size(); j++) {
                if (pSort.get(j) == intervals[i][1]+1) {
                    break;
                }
                if (flag || pSort.get(j) == intervals[i][0]) {
                    flag = true;
                    items.get(j).add(i+1);
                }

            }
        }
        long[] dp = new long[N+1];
        dp[0] = 1;
        for (int i = 0; i < pSort.size()-1; i++) {
            long[] pref = new long[N+1];
            pref[0] = dp[0];
            for (int j = 1; j <= N; j++) {
                pref[j] = dp[j] + pref[j-1];
            }
            ArrayList<Integer> item = items.get(i);
            long[] pathCount = new long[item.size()];
            long sz = pSort.get(i+1) - pSort.get(i);
            long[] szCount = new long[item.size()];
            szCount[0] = (sz*(sz-1))/2;
            for (int j = 1; j < item.size(); j++) {
                szCount[j] = szCount[j-1]*(sz - j - 1)*inverse[j+2];
            }
            for (int j = 1; j < item.size(); j++) {
                for (int k = 0; k < j; k++) {
                    pathCount[j] += szCount[k] * choose[j-1][k];
                }
            }
            pathCount[0] = sz;
            for (int j = 0; j < item.size(); j++) {
                for (int d = 0; d <= j; d++) {
                    dp[item.get(j)] += pathCount[d]*pref[item.get(j-d)-1];
                }
            }
        }
        long tot = 0;
        for (int i = 1; i < dp.length; i++) {
            tot += dp[i];
        }
        out.println(tot);
        out.close();
    }
    static long MOD = (int)(1e9) + 7;

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public String nextLine() {
            try {
                return reader.readLine();
            }
            catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 15156 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 15156 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 15144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 166 ms 15156 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -