Submission #263623

#	Time	Username	Problem	Language	Result	Execution time	Memory
263623		ijxjdjd	Boat (APIO16_boat)	Java	0 / 100	79 ms	12292 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;
    }
    
    @SuppressWarnings("unchecked")
    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<Integer>[] items = new ArrayList[pSort.size()];
//        for (int i = 0; i < pSort.size(); i++) {
//            items[i] = new ArrayList<Integer>();
//        }
//        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[items[i].get(j)] += pathCount[d]*pref[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());
        }
    }
}

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