Submission #263627

#	Time	Username	Problem	Language	Result	Execution time	Memory
263627		ijxjdjd	Boat (APIO16_boat)	Java	0 / 100	165 ms	14952 KiB

boat

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[] items = new ArrayList[pSort.size()];
        for (int i = 0; i < pSort.size(); i++) {
            items[i] = 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[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];
            }
            long[] pathCount = new long[items[i].size()];
            long sz = pSort.get(i+1) - pSort.get(i);
            long[] szCount = new long[items[i].size()];
            szCount[0] = (sz*(sz-1))/2;
            for (int j = 1; j < items[i].size(); j++) {
                szCount[j] = szCount[j-1]*(sz - j - 1)*inverse[j+2];
            }
            for (int j = 1; j < items[i].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 < items[i].size(); j++) {
                for (int d = 0; d <= j; d++) {
                    dp[(int)items[i].get(j)] += pathCount[d]*pref[(int)items[i].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());
        }
    }
}

Compilation message (stderr)

Note: boat.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42