Submission #1341482

#TimeUsernameProblemLanguageResultExecution timeMemory
1341482manubnBoat (APIO16_boat)Java
Compilation error
0 ms0 KiB
/* ----------------------------------------------------------------------------  */
/*   ( The Authentic JAVA/Python/JS CodeBuff )
 ___ _                      _              _ 
 | _ ) |_  __ _ _ _ __ _ __| |_ __ ____ _ (_)
 | _ \ ' \/ _` | '_/ _` / _` \ V  V / _` || |
 |___/_||_\__,_|_| \__,_\__,_|\_/\_/\__,_|/ |
                                        |__/ 
 */
/* --------------------------------------------------------------------------   */
/*    Youtube: https://youtube.com/@code-with-Bharadwaj                        */
/*    Github : https://github.com/Manu577228                                  */
/*    Portfolio : https://manu-bharadwaj-portfolio.vercel.app/portfolio      */
/* -----------------------------------------------------------------------  */

import java.io.*;
import java.util.*;

public class Main {
    static final int MOD = 1000000007;

    static long add(long a, long b) {
        a += b;
        if (a >= MOD) a -= MOD;
        return a;
    }

    static long mul(long a, long b) {
        return (a * b) % MOD;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int n = Integer.parseInt(br.readLine());
        int[] l = new int[n];
        int[] r = new int[n];

        TreeSet<Integer> set = new TreeSet<>();

        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");
            l[i] = Integer.parseInt(s[0]);
            r[i] = Integer.parseInt(s[1]);
            set.add(l[i]);
            set.add(r[i] + 1);
        }

        int m = set.size();
        int[] vals = new int[m];
        int idx = 0;
        for (int v : set) vals[idx++] = v;

        long[] dp = new long[n + 1];
        dp[0] = 1;

        for (int i = 0; i < m - 1; i++) {
            int L = vals[i];
            int R = vals[i + 1] - 1;
            int len = R - L + 1;

            int cnt = 0;
            for (int j = 0; j < n; j++) {
                if (l[j] <= L && r[j] >= R) cnt++;
            }

            if (cnt == 0) continue;

            long[] ndp = new long[n + 1];

            for (int used = 0; used <= n; used++) {
                if (dp[used] == 0) continue;

                long ways = 1;

                for (int take = 0; take <= cnt && used + take <= n; take++) {
                    if (take > len) break;

                    if (take > 0) {
                        ways = mul(ways, (len - take + 1));
                        ways = mul(ways, inv(take));
                    }

                    ndp[used + take] = add(ndp[used + take], mul(dp[used], ways));
                }
            }

            dp = ndp;
        }

        long ans = 0;
        for (int i = 1; i <= n; i++) ans = add(ans, dp[i]);

        out.println(ans);
        out.flush();
    }

    static long inv(long x) {
        return pow(x, MOD - 2);
    }

    static long pow(long a, long b) {
        long r = 1;
        while (b > 0) {
            if ((b & 1) == 1) r = (r * a) % MOD;
            a = (a * a) % MOD;
            b >>= 1;
        }
        return r;
    }
}

Compilation message (stderr)

boat.java:18: error: class Main is public, should be declared in a file named Main.java
public class Main {
       ^
1 error

=======