제출 #772271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772271		sushikid	Rabbit Carrot (LMIO19_triusis)	Java	100 / 100	417 ms	31364 KiB

triusis

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

public class triusis {
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken());
        TreeMap<Long, Integer> multiset = new TreeMap<>();
        for (int i = 1; i <= n; i++) {
            int x = Integer.parseInt(r.readLine());
            long z = m * i - x;
            if(z < 0){
                continue;
            }
            if(multiset.higherKey(z) != null){
                multiset.put(multiset.higherKey(z), multiset.get(multiset.higherKey(z)) - 1);
                if(multiset.get(multiset.higherKey(z)) == 0){
                    multiset.remove(multiset.higherKey(z));
                }
            }
            multiset.put(z, multiset.getOrDefault(z, 0) + 1);
        }
        int ans = 0;
        for(int e : multiset.values()){
            ans += e;
        }
        pw.println(n - ans);
        pw.close();
    }
}

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