Skip to content

Instantly share code, notes, and snippets.

@bhi5hmaraj bhi5hmaraj/Main.java
Created Jul 26, 2017

Embed
What would you like to do?
Lazy Cows AC solution
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 ************************/
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.