Submission #1257258

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257258		wheelert	Hacker (BOI15_hac)	C++20	20 / 100	82 ms	4168 KiB

hac

#include <iostream>                                                                                                 
#include <vector>                                                                                                   
#include <deque>                                                                                                    
                                                                                                                    
                                                                                                                    
using namespace std;                                                                                                
                                                                                                                    
                                                                                                                    
int optimal_solution(vector<int> const& arr)                                                                        
{                                                                                                                   
    int N = arr.size();                                                                                             
    int num_window = ( N + 1 ) / 2;                                                                                 
    // invariant - (index, val) in window min is always sorted in increasing order of                               
    //           - querying the min can always be done by accessing front()                                         
    //                                                                                                              
    deque<pair<int, int>> window_min{};                                                                             
                                                                                                                    
    auto insert = [&](int index, int val) {                                                                         
        while (window_min.size() > 0 && window_min.back().second > val)                                             
            window_min.pop_back();                                                                                  
                                                                                                                    
        window_min.emplace_back( index, val );                                                                      
                                                                                                                    
        while (window_min.size() > 0 && window_min.front().first <= index - num_window) window_min.pop_front();     
    };                                                                                                              
                                                                                                                    
    static constexpr int INF = 1'000'000'000;                                                                       
    vector<int> min_answer_per_node(N, INF);                                                                        
    int subrange_sum = 0;                                                                                           
    for (int k = 0; k < num_window; ++k) {                                                                          
        subrange_sum += arr[(0 - num_window + 1 + k + N) % N];                                                      
    }                                                                                                               
    for (int j = 0; j < num_window; ++j) {                                                                          
        insert(j - num_window + 1, subrange_sum);                                                                   
                                                                                                                    
        int subrange_start = (j - num_window + 1 + N) % N;                                                          
        int subrange_end = j;                                                                                       
        //std::cout << "start: " << subrange_start << " end: " << subrange_end << std::endl;                        
        //std::cout << subrange_sum << endl;                                                                        
        subrange_sum += arr[(j + 1 + N) % N];                                                                       
        subrange_sum -= arr[(j - num_window + 1 + N) % N];                                                          
    }                                                                                                               
    for (int i = 0; i < N ; ++i) {                                                                                  
        min_answer_per_node[i] = window_min.front().second;                                                         
        insert(i, subrange_sum);                                                                                    
                                                                                                                    
        subrange_sum += arr[(i + num_window + N) % N];                                                              
        subrange_sum -= arr[i];                                                                                     
    }                                                                                                               
                                                                                                                    
    int answer = 0;                                                                                                 
    for (int i = 0; i < N; ++i) answer = std::max(min_answer_per_node[i], answer);                                  
    return answer;                                                                                                  
}                                                                                                                   
                                                                                                                    
// test driver                                                                                                      
int main()                                                                                                          
{                                                                                                                   
    int N;                                                                                                          
    cin >> N;                                                                                                       
    vector<int> arr(N);                                                                                             
    for (int i = 0; i < N; ++i) cin >> arr[i];                                                                      
                                                                                                                    
    std::cout << optimal_solution(arr) << std::endl;                                                                
}                                                                                                                   
                                                                                                                    

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 40