Submission #1171883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171883		lancethedragontrainer	Lightning Rod (NOI18_lightningrod)	C++20	21 / 100	928 ms	156376 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Fast I/O setup
static auto __ = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();

typedef long long ll;

// Check if building at position j can protect building at position k
inline bool canProtect(const vector<pair<ll, ll>>& buildings, int j, int k) {
    return abs(buildings[j].first - buildings[k].first) <= buildings[j].second - buildings[k].second;
}

int main() {
    int n;
    cin >> n;
    
    vector<pair<ll, ll>> buildings(n);
    for (int i = 0; i < n; i++) {
        cin >> buildings[i].first >> buildings[i].second;
    }
    
    int rodCount = 0;
    int i = 0;
    
    while (i < n) {
        // Need a new rod to protect building i
        rodCount++;
        
        // Find the building that will allow us to protect the furthest to the right
        int maxReach = i;
        
        for (int j = i; j < n; j++) {
            // Check if a rod at j can protect building i
            if (!canProtect(buildings, j, i)) {
                break; // Buildings further right can't protect i either
            }
            
            // Find how far to the right a rod at j can protect
            int k = maxReach;
            while (k + 1 < n && canProtect(buildings, j, k + 1)) {
                k++;
            }
            
            maxReach = max(maxReach, k);
        }
        
        // Skip to the next unprotected building
        i = maxReach + 1;
    }
    
    cout << rodCount << endl;
    return 0;
}

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