oj.uz

Submission #341547

# Submission time Handle Problem Language Result Execution time Memory
341547 2020-12-30T00:44:57 Z KWang31 Tents (JOI18_tents) Java 11
100 / 100
 422 ms 82100 KB 
import java.io.*; import java.util.*;
public class tents{
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        
    } 
    public static class Pair implements Comparable<Pair>{
        int vtx; int val;
        public Pair(int a, int b){
            this.vtx=a; this.val=b;
        }
        public int compareTo(Pair other){
            if(this.val<other.val)return -1;
            if(this.val>other.val)return 1;
            if(this.vtx<other.vtx)return -1;
            return 1;
        }
    }
    static int MOD=1000000007;
    static int[] rk, p,siz;
    public static void main(String[] args){
        FastReader br=new FastReader();
        int N=br.nextInt(); int M=br.nextInt();
        long[][] dp=new long[N+1][M+1];
        for (int i = 0; i <=N; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i <=M; i++) {
            dp[0][i]=1;
        }
        for (int x = 1; x <=N; x++) {
            for (int y = 1; y <=M; y++) {//x rows, y columns
                dp[x][y]=dp[x][y-1];
                if(x>=2){dp[x][y]+=(x*(x-1)/2)*dp[x-2][y-1]; dp[x][y]%=MOD;}
                dp[x][y]+=dp[x-1][y-1]*4*x; dp[x][y]%=MOD;
                if(y>=2)dp[x][y]+=dp[x-1][y-2]*x*(y-1); dp[x][y]%=MOD;
            }
        }
        System.out.println(dp[N][M]-1);
    }
    
    public static int find(int x, int[] p){
        if(p[x]==x)return x;
        int ans=find(p[x],p); p[x]=ans; return ans;
    }
    
    public static void merge(int a, int b) {
        if(rk[a]<rk[b]) {
            p[a]=b; siz[b]+=siz[a];
        }else if(rk[a]==rk[b]) {
            p[a]=b; rk[b]++;siz[b]+=siz[a];
        }else {
            p[b]=a; siz[a]+=siz[b];
        }
    }
    
}
//Debugging:
//Are you sure your algorithm is correct?
//Bounds: long
//Special cases: n=0,1?
//Make sure you remove your debugging code before you submit!

Subtask #1
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8496 KB Output is correct
2 Correct 72 ms 8580 KB Output is correct
3 Correct 73 ms 8556 KB Output is correct
4 Correct 72 ms 8552 KB Output is correct
5 Correct 88 ms 9348 KB Output is correct
6 Correct 86 ms 9452 KB Output is correct
7 Correct 100 ms 9324 KB Output is correct
8 Correct 87 ms 9452 KB Output is correct
9 Correct 74 ms 8528 KB Output is correct
10 Correct 86 ms 9452 KB Output is correct
11 Correct 75 ms 8552 KB Output is correct
12 Correct 88 ms 10076 KB Output is correct

Subtask #2
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 8496 KB Output is correct
2 Correct 72 ms 8580 KB Output is correct
3 Correct 73 ms 8556 KB Output is correct
4 Correct 72 ms 8552 KB Output is correct
5 Correct 88 ms 9348 KB Output is correct
6 Correct 86 ms 9452 KB Output is correct
7 Correct 100 ms 9324 KB Output is correct
8 Correct 87 ms 9452 KB Output is correct
9 Correct 74 ms 8528 KB Output is correct
10 Correct 86 ms 9452 KB Output is correct
11 Correct 75 ms 8552 KB Output is correct
12 Correct 88 ms 10076 KB Output is correct
13 Correct 72 ms 8704 KB Output is correct
14 Correct 73 ms 8560 KB Output is correct
15 Correct 300 ms 53588 KB Output is correct
16 Correct 101 ms 13008 KB Output is correct
17 Correct 138 ms 23012 KB Output is correct
18 Correct 143 ms 22976 KB Output is correct
19 Correct 338 ms 81360 KB Output is correct
20 Correct 288 ms 51676 KB Output is correct
21 Correct 214 ms 40912 KB Output is correct
22 Correct 234 ms 41296 KB Output is correct
23 Correct 161 ms 27696 KB Output is correct
24 Correct 422 ms 81344 KB Output is correct
25 Correct 348 ms 81984 KB Output is correct
26 Correct 384 ms 81488 KB Output is correct
27 Correct 412 ms 82100 KB Output is correct