제출 #366244

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
366244		dapig	Rabbit Carrot (LMIO19_triusis)	Java	100 / 100	293 ms	17872 KiB

triusis

//package lis;

import java.io.*;
import java.util.*;

class triusis {

	public static void main(String[] args) throws IOException {

		triusis obj = new triusis();

		obj.doStuff();

	}
	
	boolean check(int val, int m) {
		long v1 = nums[lis[m]];
		long v2 = nums[val];
		v2 -= (val-lis[m])*inc;
		return (v1 >= v2);
	}
	
	int bs(int val) {
		int l = 0, r = count;
		while (l < r) {
			int m = (l+r)/2;
			if (check(val, m)) {
				if (lis[m+1]==-1) return m;
				if (!check(val, m+1)) return m;
				l = m+1;
			} else r = m;
		}
		if (l==0) return (check(val, 0)) ? 0 : -1;
		return l;
	}
	
	int[] lis; int count = 0;
	void lis() {
		lis = new int[nums.length+1];
		Arrays.fill(lis, -1);
		lis[0] = 0;
		for (int i = 1; i < nums.length; i++) {
			int pos = bs(i)+1;
			if (pos==0) continue;
			if (pos > count) count = pos;
			lis[pos] = i;
		}
	}

	long[] nums;
	long inc;
	private void doStuff() throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		nums = new long[Integer.parseInt(st.nextToken())+1];
		inc = Integer.parseInt(st.nextToken());
		for (int i = 1; i < nums.length; i++) {
			nums[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		
		lis();
		
		System.out.println(nums.length-1-count);

	}

}

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