Submission #1341484

#TimeUsernameProblemLanguageResultExecution timeMemory
1341484manubnBoat (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[] fact, invFact;

    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;
    }

    static long C(int n, int r) {
        if (r < 0 || r > n) return 0;
        return fact[n] * invFact[r] % MOD * invFact[n - r] % 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;

        int MAX = n + 5;

        fact = new long[MAX];
        invFact = new long[MAX];

        fact[0] = 1;
        for (int i = 1; i < MAX; i++) fact[i] = fact[i - 1] * i % MOD;

        invFact[MAX - 1] = pow(fact[MAX - 1], MOD - 2);
        for (int i = MAX - 2; i >= 0; i--) invFact[i] = invFact[i + 1] * (i + 1) % MOD;

        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;

                for (int take = 0; take <= cnt && used + take <= n; take++) {
                    long ways = C(len, take);
                    ndp[used + take] = (ndp[used + take] + dp[used] * ways) % MOD;
                }
            }

            dp = ndp;
        }

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

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

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

=======