제출 #1181756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181756		mehmetkagan	Solar Storm (NOI20_solarstorm)	C++20	8 / 100	1651 ms	117780 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_module(N + 1, 0); // 1-based indexing
    for(int i = 2; i <= N; ++i){
        x_module[i] = x_module[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_module[j] - x_module[i] <= K)){
            j++;
        }
        end_idx[i] = j -1;
    }
    
    // Precompute jump pointers for binary lifting
    int LOG = 20; // since 2^20 > 1e6
    vector<vector<int>> dp(LOG, vector<int>(N +2, N +1)); // dp[k][i]
    
    // Base case: 2^0 =1 shield
    for(int i=1; i<=N; ++i){
        dp[0][i] = end_idx[i] +1;
    }
    
    // Build the sparse table
    for(int k =1; k < LOG; ++k){
        for(int i=1; i<=N; ++i){
            if(dp[k-1][i] <= N){
                dp[k][i] = dp[k-1][dp[k-1][i]];
            }
            else{
                dp[k][i] = N +1;
            }
        }
    }
    
    // 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;
        for(int k = LOG -1; k >=0; --k){
            if(dp[k][pos] <= r){
                pos = dp[k][pos];
                count += (1 <<k);
            }
        }
        if(pos <= r){
            count +=1;
        }
        return count;
    };
    
    // Compute prefix sums
    vector<ll> prefix_sum(N +1, 0);
    for(int i=1; i<=N; ++i){
        prefix_sum[i] = prefix_sum[i-1] + v[i];
    }
    
    // Find the optimal interval [best_l, best_r]
    ll max_sum = 0;
    int best_l =1, best_r =1;
    
    for(int l =1; l <=N; ++l){
        int low = l, high = N, best_r_current = l;
        while(low <= high){
            int mid = low + (high - low)/2;
            if(shields_needed(l, mid) <= 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;
        }
    }
    
    // Place shields within [best_l, best_r]
    vector<int> shield_positions;
    int pos = best_l;
    while(pos <= best_r && (int)shield_positions.size() < S){
        // Place the shield at the farthest possible position within [pos, best_r]
        int shield_pos = end_idx[pos];
        shield_pos = min(shield_pos, best_r);
        shield_positions.push_back(shield_pos);
        pos = shield_pos +1;
    }
    
    // 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: 0 / 10
• Subtask 2: 0 / 7
• Subtask 3: 0 / 11
• Subtask 4: 8 / 8
• Subtask 5: 0 / 18
• Subtask 6: 0 / 16
• Subtask 7: 0 / 30