Submission #1160229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160229		siegeonsticks	Rabbit Carrot (LMIO19_triusis)	Java	100 / 100	176 ms	33420 KiB

triusis

import java.io.*;
import java.util.*;
public class triusis {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		ArrayList<Integer> a = new ArrayList<>();
		for (int i=0; i<n; i++) {
			int p = Integer.parseInt(br.readLine());
			if ((i+1)*m>=p) a.add((i+1)*m-p);
		}
		pw.println(n-subseq(a));
		pw.close();
	}
	private static int subseq(ArrayList<Integer> arr) {
		ArrayList<Integer> mend = new ArrayList<>();
		for (int i:arr) {
			int pos = bisect(mend, i);
			if (pos==mend.size()) mend.add(i);
			else mend.set(pos, i);
		}
		return mend.size();
	}
	private static int bisect(ArrayList<Integer> arr, int x) {
		int lo = 0, hi = arr.size();
		while (lo<hi) {
			int mid = (lo+hi)/2;
			if (x<arr.get(mid)) hi = mid;
			else lo = mid+1;
		}
		return lo;
	}
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37