Skip to content

Instantly share code, notes, and snippets.

@bhi5hmaraj bhi5hmaraj/Main.java
Last active Jul 23, 2017

Embed
What would you like to do?
import java.util.*;
import java.io.*;
public class Main {
/************************ SOLUTION STARTS HERE ************************/
static final int INF = (int) 1e9;
private static void solve() {
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);
// Sorts the entries in ascending order of columns and breaking ties with row
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];
}
});
int sz = 1;
for(int i = 1; i < N; i++)
sz += arr[i][1] != arr[i - 1][1] ? 1 : 0;
/*
The compress array stores one entry for each column
compress[i][0] = ith smallest column
compress[i][1] = 0 - only up , 1 - only down , 2 - both
*/
int compress[][] = new int[sz][2];
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++;
}
}
int[][] costH1 = new int[sz][sz]; // one horizontal rect ----
int[][] costH2 = new int[sz][sz]; // two horizontal rect ====
int[][] costV = new int[sz][sz]; // one vertical rect | |
for(int i = 0; i < sz; i++) {
int firstUp = 0 , firstDown = 0;
int lastUp = -1 , lastDown = -1;
costH1[i][i] = compress[i][1] == 2 ? INF : 1;
costH2[i][i] = compress[i][1] == 2 ? 2 : INF;
costV[i][i] = 2;
int first = compress[i][1];
boolean flag = compress[i][1] != 2;
if(compress[i][1] != 1)
firstUp = lastUp = compress[i][0];
if(compress[i][1] != 0)
firstDown = lastDown = compress[i][0];
for(int j = i + 1; j < sz; j++) {
costV[i][j] = 2 * (compress[j][0] - compress[i][0] + 1);
flag &= compress[j][1] == first;
costH1[i][j] = flag ? compress[j][0] - compress[i][0] + 1 : INF;
if(firstUp == 0 && compress[j][1] != 1)
firstUp = lastUp = compress[j][0];
if(firstDown == 0 && compress[j][1] != 0)
firstDown = lastDown = compress[j][0];
lastUp = compress[j][1] != 1 ? compress[j][0] : lastUp;
lastDown = compress[j][1] != 0 ? compress[j][0] : lastDown;
costH2[i][j] = flag ? INF : (lastUp - firstUp + 1) + (lastDown - firstDown + 1);
}
}
int DP[][] = new int[K + 1][sz];
Arrays.fill(DP[0], INF);
for(int i = 0; i < sz; i++)
DP[1][i] = Math.min(costV[0][i] , costH1[0][i]);
for(int i = 2; i <= K; i++) {
for(int j = 0; j < sz; j++) {
DP[i][j] = INF;
for(int k = -1; k < j; k++) {
int dp1 = k == -1 ? 0 : DP[i - 1][k];
int dp2 = k == -1 ? 0 : DP[i - 2][k];
DP[i][j] = Math.min(DP[i][j] , dp1 + Math.min(costV[k + 1][j] , costH1[k + 1][j]));
DP[i][j] = Math.min(DP[i][j] , dp2 + costH2[k + 1][j]);
}
}
}
println(DP[K][sz - 1]);
}
/************************ 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;
solve();
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.