Submission #1171882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171882		lancethedragontrainer	Lightning Rod (NOI18_lightningrod)	C++20	66 / 100	1099 ms	156232 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
typedef long long ll;
 
struct Building {
    ll A; // X - Y
    ll B; // X + Y
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
    vector<Building> buildings(n);
    for (int i = 0; i < n; i++){
        ll X, Y;
        cin >> X >> Y;
        buildings[i].A = X - Y;
        buildings[i].B = X + Y;
    }
    // Sort by B descending. For equal B, sort by A ascending.
    sort(buildings.begin(), buildings.end(), [](const Building &a, const Building &b) {
        if(a.B == b.B) return a.A < b.A;
        return a.B > b.B;
    });
 
    ll bestA = LLONG_MAX; // best (smallest) A among chosen rods
    int ans = 0;
    for(auto &b : buildings){
        // A building is covered by some rod if some chosen rod's A <= its A.
        if(bestA <= b.A)
            continue;
        // Otherwise, plant a rod here and update bestA.
        ans++;
        bestA = b.A;
    }
 
    cout << ans << "\n";
    return 0;
}

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