Submission #1181753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181753		mehmetkagan	Solar Storm (NOI20_solarstorm)	C++20	10 / 100	2094 ms	31556 KiB

SolarStorm

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

typedef long long ll;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N, S;
    ll K;
    cin >> N >> S >> K;
    
    vector<ll> d(N-1);
    for(auto &x: d) cin >> x;
    
    // Compute positions
    vector<ll> x(N+1, 0); // 1-based
    for(int i=2;i<=N;i++) x[i] = x[i-1] + d[i-2];
    
    // Read vi
    vector<int> v(N+1, 0);
    for(int i=1;i<=N;i++) cin >> v[i];
    
    // Compute end[i]: farthest module covered by a shield at i
    vector<int> end_idx(N+1, 0);
    int j=1;
    for(int i=1;i<=N;i++){
        while(j <=N && x[j] <=x[i] + K){
            j++;
        }
        end_idx[i] =j-1;
    }
    
    // Compute prefix sum
    vector<ll> prefix_sum(N+1, 0);
    for(int i=1;i<=N;i++) prefix_sum[i] = prefix_sum[i-1] + v[i];
    
    // Function to compute minimal number of shields to cover [l, r]
    auto shields_needed = [&](int l, int r) -> int {
        int count =0;
        int pos = l;
        while(pos <= r){
            // Place shield as far to the right as possible
            int shield_pos = end_idx[pos];
            if(shield_pos < pos){
                // Cannot cover this position
                return S +1;
            }
            count++;
            pos = end_idx[shield_pos] +1;
        }
        return count;
    };
    
    // Now, iterate over all possible l, and find the maximum sum [l, r] where shields_needed(l, r) <= S
    // To optimize, use binary search for each l to find the maximum r
    ll max_sum = 0;
    int best_l =1, best_r=1;
    
    for(int l=1; l<=N; l++){
        // Binary search for r from current r_min to N
        int low = l, high = N, best_r_current = l;
        while(low <= high){
            int mid = low + (high - low)/2;
            int required = shields_needed(l, mid);
            if(required <= S){
                best_r_current = mid;
                low = mid +1;
            }
            else{
                high = mid -1;
            }
        }
        // Compute the sum for [l, best_r_current]
        ll current_sum = prefix_sum[best_r_current] - prefix_sum[l-1];
        if(current_sum > max_sum){
            max_sum = current_sum;
            best_l = l;
            best_r = best_r_current;
        }
    }
    
    // Now, place shields within [best_l, best_r]
    vector<int> shield_positions;
    int pos = best_l;
    while(pos <= best_r && shield_positions.size() < S){
        int shield_pos = end_idx[pos];
        if(shield_pos > best_r){
            shield_pos = best_r;
            // Ensure it covers pos
            while(shield_pos >= pos && x[shield_pos] - x[pos] > K){
                shield_pos--;
            }
            if(shield_pos < pos){
                // Cannot cover this position
                break;
            }
        }
        shield_positions.push_back(shield_pos);
        pos = end_idx[shield_pos] +1;
    }
    
    // If we have not used all shields, we can leave some shields unused
    // Or, to spread them for better coverage, but it's optional
    
    // Output
    cout << shield_positions.size() << "\n";
    for(int i=0;i<shield_positions.size();i++){
        cout << shield_positions[i] << (i < shield_positions.size()-1 ? " ":"\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