Submission #1297184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1297184		chaitanyamehta	Lightning Rod (NOI18_lightningrod)	C++20	66 / 100	1100 ms	161484 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    if (!(cin >> N)) return 0;
    vector<pair<int64,int64>> v;
    v.reserve((size_t)N);
    
    for (int i = 0; i < N; ++i) {
        int64 X, Y;
        cin >> X >> Y;
        int64 A = X + Y;
        int64 B = X - Y;
        v.emplace_back(A, B);
    }
    
    // sort by A descending, break ties by B ascending
    sort(v.begin(), v.end(), [](const pair<int64,int64>& p1, const pair<int64,int64>& p2){
        if (p1.first != p2.first) return p1.first > p2.first;
        return p1.second < p2.second;
    });
    
    int64 minB_selected = (int64)9e18; // +inf
    int64 rods = 0;
    for (auto &p : v) {
        int64 B = p.second;
        if (minB_selected <= B) {
            // already covered by a previously chosen rod
            continue;
        } else {
            // must place rod here
            ++rods;
            minB_selected = B;
        }
    }
    
    cout << rods << '\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