Submission #1171884

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171884		lancethedragontrainer	Lightning Rod (NOI18_lightningrod)	Java	80 / 100	3103 ms	524320 KiB

Main

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

public class Main {
    static class Building {
        long A; // X - Y
        long B; // X + Y
        
        public Building(long A, long B) {
            this.A = A;
            this.B = B;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // Read the number of buildings.
        int n = Integer.parseInt(br.readLine().trim());
        Building[] buildings = new Building[n];
        
        // Read building coordinates and compute A and B.
        for (int i = 0; i < n; i++) {
            String[] tokens = br.readLine().split(" ");
            long X = Long.parseLong(tokens[0]);
            long Y = Long.parseLong(tokens[1]);
            buildings[i] = new Building(X - Y, X + Y);
        }
        
        // Sort buildings by B descending; if B's are equal, sort by A ascending.
        Arrays.sort(buildings, new Comparator<Building>() {
            @Override
            public int compare(Building b1, Building b2) {
                if (b1.B == b2.B)
                    return Long.compare(b1.A, b2.A);
                return Long.compare(b2.B, b1.B);
            }
        });
        
        // Greedy selection of buildings to plant lightning rods.
        long bestA = Long.MAX_VALUE;
        int ans = 0;
        for (Building b : buildings) {
            // If bestA is already less than or equal to the current building's A,
            // it means this building is protected by an earlier chosen rod.
            if (bestA <= b.A)
                continue;
            // Otherwise, plant a rod here and update bestA.
            ans++;
            bestA = b.A;
        }
        
        System.out.println(ans);
    }
}

• Subtask 1: 4 / 4
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 21 / 21
• Subtask 5: 26 / 26
• Subtask 6: 10 / 10
• Subtask 7: 0 / 20