Submission #1128029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128029		Oz121	Rabbit Carrot (LMIO19_triusis)	Java	100 / 100	414 ms	60404 KiB

triusis

import java.io.*;
import java.util.*;
public class triusis {
    public static void main(String[] args) throws IOException {
        BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer l1 = new StringTokenizer(scan.readLine()); int num = Integer.parseInt(l1.nextToken()); int jump = Integer.parseInt(l1.nextToken());
        int[] arr = new int[num];
        for (int i = 0;i<num;i++) {
            StringTokenizer st = new StringTokenizer(scan.readLine());
            arr[num-1-i] = Integer.parseInt(st.nextToken())-(i+1)*jump;
        }
        //System.out.println(Arrays.toString(arr));

        //Find the longest non-increasing subsequence = longest non-decreasing subsequence of reversed array
        ArrayList<Integer> dp = new ArrayList<>();
        HashMap<Integer, Integer> largeIdx = new HashMap<>(); //maps the possible dp[i] values to their largest i
        for (int i = 0;i<num;i++) {
            int pos = Collections.binarySearch(dp, arr[i]);

            if (pos<0) pos = (-1)*pos-1;
            else pos = largeIdx.get(arr[i])+1;

            if (pos==dp.size()) {
                dp.add(arr[i]); largeIdx.put(arr[i],dp.size()-1);
            } else {
                //if (pos==0)
                dp.set(pos, arr[i]); largeIdx.put(arr[i], Math.max(largeIdx.getOrDefault(arr[i],0), pos));
            }
        }

        int ans = -1;
        for (int i = 0;i<dp.size();i++) {
            if (dp.get(i)<=0) ans = i;
        }
        System.out.println(num-ans-1);
    }
}

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