제출 #1128393

#제출 시각아이디문제언어결과실행 시간메모리
1128393Oz121Global Warming (CEOI18_glo)Java
32 / 100
371 ms55528 KiB
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[0][0], sLIS[num-1][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);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...