Submission #1181854

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181854		mehmetkagan	Solar Storm (NOI20_solarstorm)	C++17	10 / 100	2093 ms	61636 KiB

SolarStorm

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

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n, s;
    ll k;
    cin >> n >> s >> k;

    vector<ll> dist(n), pos(n);
    for (int i = 1; i < n; i++) {
        cin >> dist[i];
        pos[i] = pos[i - 1] + dist[i];
    }

    vector<int> val(n);
    for (int i = 0; i < n; i++) cin >> val[i];

    // Step 1: Build intervals for each possible shield placement
    vector<pair<int, int>> intervals(n); // [l, r] coverage range
    for (int i = 0; i < n; i++) {
        int l = i, r = i;
        // Expand left
        while (l > 0 && pos[i] - pos[l - 1] <= k) l--;
        // Expand right
        while (r + 1 < n && pos[r + 1] - pos[i] <= k) r++;
        intervals[i] = {l, r};
    }

    // Step 2: Greedy interval covering with highest value sum
    vector<pair<int, int>> shields; // (total value, position)
    for (int i = 0; i < n; i++) {
        int total = 0;
        for (int j = intervals[i].first; j <= intervals[i].second; j++) {
            total += val[j];
        }
        shields.push_back({total, i});
    }

    // Sort by total value descending
    sort(shields.rbegin(), shields.rend());

    vector<bool> covered(n, false);
    vector<int> answer;
    int used = 0;

    for (auto [total, idx] : shields) {
        if (used == s) break;

        int l = intervals[idx].first, r = intervals[idx].second;
        bool already_covered = true;
        for (int i = l; i <= r; i++) {
            if (!covered[i]) {
                already_covered = false;
                break;
            }
        }
        if (!already_covered) {
            answer.push_back(idx + 1); // +1 for 1-based output
            for (int i = l; i <= r; i++) covered[i] = true;
            used++;
        }
    }

    // Step 3: Ensure the covered range is continuous
    int first = 0;
    while (first < n && !covered[first]) first++;
    int last = n - 1;
    while (last >= 0 && !covered[last]) last--;
    for (int i = first; i <= last; i++) {
        if (!covered[i]) {
            // Not fully connected, force connectivity by adding shield
            answer.push_back(i + 1);
            for (int j = intervals[i].first; j <= intervals[i].second; j++) {
                covered[j] = true;
            }
            used++;
            if (used > s) break; // Can't exceed shield count
        }
    }

    cout << answer.size() << '\n';
    for (int x : answer) cout << x << ' ';
    cout << '\n';

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 0 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30