Lazy Cows AC solution

Main.java

import java.util.*;
import java.io.*;
public class Main {
    
    
    
    /************************ SOLUTION STARTS HERE ************************/
    
    static final int INF = (int) 1e9;
    static int compress[][];
    static int sz;
    static int memo[][][];
  
    static int rec(int idx , int rem , int hUp , int hDown , int v) {
        int mask = (hUp << 2) | (hDown << 1) | v;
        if(rem < 0)
            return INF;
        else if(idx == sz - 1)
            return 0;
        else if(memo[idx][rem][mask] != -1)
            return memo[idx][rem][mask];
        else {
            int min = INF;
            // Create new rectangle
            if(compress[idx + 1][1] == 0) 
                min = Math.min(min , 1 + rec(idx + 1, rem - 1, 1, 0, 0));
            if(compress[idx + 1][1] == 1)
                min = Math.min(min , 1 + rec(idx + 1, rem - 1, 0, 1, 0));
            if(compress[idx + 1][1] == 2)
                min = Math.min(min , 2 + rec(idx + 1, rem - 2, 1, 1, 0));
            
            min = Math.min(min , 2 + rec(idx + 1, rem - 1, 0, 0, 1));
            
            // Extend
            if(v == 1)
                min = Math.min(min , 2 * (compress[idx + 1][0] - compress[idx][0]) + 
                                         rec(idx + 1, rem, 0, 0, 1));
            else if(hUp == 1 && hDown == 0) {
                if(compress[idx + 1][1] == 0)
                    min = Math.min(min , (compress[idx + 1][0] - compress[idx][0])
                                        + rec(idx + 1, rem, 1, 0, 0));
                else
                    min = Math.min(min , (compress[idx + 1][0] - compress[idx][0]) + 1
                                        + rec(idx + 1, rem - 1, 1, 1, 0));
            }
            else if(hUp == 0 && hDown == 1) {
                if(compress[idx + 1][1] == 1)
                    min = Math.min(min , (compress[idx + 1][0] - compress[idx][0])
                                        + rec(idx + 1, rem, 0, 1, 0));
                else
                    min = Math.min(min , (compress[idx + 1][0] - compress[idx][0]) + 1
                                        + rec(idx + 1, rem - 1, 1, 1, 0));
            }
            else {
                if(compress[idx + 1][1] == 0)
                    min = Math.min(min , (compress[idx + 1][0] - compress[idx][0])
                                        + rec(idx + 1, rem, 1, 0, 0));
                else if(compress[idx + 1][1] == 1)
                    min = Math.min(min , (compress[idx + 1][0] - compress[idx][0])
                                        + rec(idx + 1, rem, 0, 1, 0));
                
                min = Math.min(min , 2 * (compress[idx + 1][0] - compress[idx][0]) 
                                        + rec(idx + 1, rem, 1, 1, 0));
            }
            
            return memo[idx][rem][mask] = min;
        }
    }
    
    private static void solve2() {
        
        int N = nextInt();
        int K = nextInt();
        int B = nextInt();
        
        int arr[][] = new int[N][];
        for(int i = 0; i < N; i++)
            arr[i] = nextIntArray(2);
        
        
        // long st = System.nanoTime();
        
        Arrays.sort(arr , new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[1] != o2[1])
                    return o1[1] - o2[1];
                else
                    return o1[0] - o2[0];
            }
        });
        
        sz = 1;
        for(int i = 1; i < N; i++)
            sz += arr[i][1] != arr[i - 1][1] ? 1 : 0;
        
        compress = new int[sz][2]; // 0 - up , 1 - down , 2 - both
        int ptr = 0;
        for(int i = 0; i < N; ) {
            compress[ptr][0] = arr[i][1];
            if(i + 1 < N && arr[i][1] == arr[i + 1][1]) {
                compress[ptr++][1] = 2;
                i += 2;
            } else {
                compress[ptr++][1] = arr[i][0] - 1;
                i++;
            }
        }
        
        memo = new int[sz][K][8];
        for(int a[][] : memo)
            for(int b[] : a)
                Arrays.fill(b, -1);
        
        int min = INF;
        if(compress[0][1] == 0)
            min = Math.min(min , 1 + rec(0, K - 1, 1, 0, 0));
        else if(compress[0][1] == 1)
            min = Math.min(min , 1 + rec(0, K - 1, 0, 1, 0));
        else
            min = Math.min(min , 2 + rec(0, K - 2, 1, 1, 0));
        
        min = Math.min(min , 2 + rec(0, K - 1, 0, 0, 1));
        
        println(min);
 }
    
    
    /************************ SOLUTION ENDS HERE ************************/
    
    
    
    
    
    /************************ TEMPLATE STARTS HERE **********************/
    
    public static void main(String[] args) throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false);
        st     = null;
        solve2();
        reader.close();
        writer.close();
    }
    
    static BufferedReader reader;
    static PrintWriter    writer;
    static StringTokenizer st;
    
    static String next()
    {while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}            
    st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
    static String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}             
    static int    nextInt()   {return Integer.parseInt(next());}
    static long   nextLong()  {return Long.parseLong(next());}     
    static double nextDouble(){return Double.parseDouble(next());}
    static char   nextChar()  {return next().charAt(0);}
    static int[]  nextIntArray(int n)         {int[] a= new int[n];   int i=0;while(i<n){a[i++]=nextInt();}  return a;}
    static long[] nextLongArray(int n)        {long[]a= new long[n];  int i=0;while(i<n){a[i++]=nextLong();} return a;}    
    static int[]  nextIntArrayOneBased(int n) {int[] a= new int[n+1]; int i=1;while(i<=n){a[i++]=nextInt();} return a;}            
    static long[] nextLongArrayOneBased(int n){long[]a= new long[n+1];int i=1;while(i<=n){a[i++]=nextLong();}return a;}            
    static void   print(Object o)  { writer.print(o);  }
    static void   println(Object o){ writer.println(o);}
    
    /************************ TEMPLATE ENDS HERE ************************/
    
}