Submission #1128024

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128024		Oz121	Rabbit Carrot (LMIO19_triusis)	Java	14 / 100	93 ms	12356 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*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()) {
                if (!dp.isEmpty()||arr[i]<=0) {
                    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));
            }
        }
        System.out.println(num-dp.size());
    }
}

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