Submission #1128394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128394		Oz121	Global Warming (CEOI18_glo)	Java	62 / 100	353 ms	55564 KiB

glo

import java.io.*;
import java.util.*;
public class glo {
    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 x = Integer.parseInt(l1.nextToken());
        int[] arr = new int[num]; StringTokenizer st = new StringTokenizer(scan.readLine());
        for (int i = 0;i<num;i++) arr[i] = Integer.parseInt(st.nextToken());

        int[][] pLIS = new int[num][2]; //For each i, store the LIS up to i and the smallest number it ends on
        ArrayList<Integer> dp = new ArrayList<>();
        for (int i = 0;i<num;i++) {
            int pos = Collections.binarySearch(dp, arr[i]);
            if (pos<0) pos = (-1)*pos-1;

            if (pos==dp.size()) dp.add(arr[i]);
            else dp.set(pos, arr[i]);

            pLIS[i][0] = dp.size();
            pLIS[i][1] = dp.get(dp.size()-1);
        }

        int[][] sLIS = new int[num][2]; //For each i, store the LIS from i->num-1 and the largest number it starts on
        dp = new ArrayList<>();
        for (int i = num-1;i>=0;i--) {
            int pos = Collections.binarySearch(dp, arr[i], (k,j)->j-k);
            if (pos<0) pos = (-1)*pos-1;

            if (pos==dp.size()) dp.add(arr[i]);
            else dp.set(pos, arr[i]);

            sLIS[i][0] = dp.size();
            sLIS[i][1] = dp.get(dp.size()-1);
        }

        int ans = Math.max(pLIS[num-1][0], sLIS[0][0]);
        for (int i = 0;i<num-1;i++) {
            if (pLIS[i][1]-x<sLIS[i+1][1]) {
                ans = Math.max(ans, pLIS[i][0]+sLIS[i+1][0]);
            }
        }
        System.out.println(ans);
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 0 / 25