Submission #1184253

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184253		kedimestan	Progression (NOI20_progression)	C++20	0 / 100	20 ms	7496 KiB

Progression

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
using ll = long long;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    // 1-indexed dizi: a[1..n]
    vector<ll> a(n+1);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    
    // dp[i] = min_{1<=l<=i} { dp[l-1] + max(a[l..i]) }
    // dp[0] = 0
    vector<ll> dp(n+1, LLONG_MAX);
    dp[0] = 0;
    
    // prefix_max[i] = max(a[1..i])
    vector<ll> prefix_max(n+1, 0);
    for (int i = 1; i <= n; i++){
        prefix_max[i] = (i==1 ? a[i] : max(prefix_max[i-1], a[i]));
    }
    
    // Stack (indeksler) – bu stack üzerinde, aday partition noktalarını (başlangıç indexleri) 
    // monotonic (azalan) a[] değerlerine göre tutacağız.
    // Yani, stack’in tepesinde en son eklenen, “küçük” bir a[i] olacak.
    vector<int> st;  
    // İşleyelim: i = 1'den n'e kadar
    for (int i = 1; i <= n; i++){
        // Her partition için; direkt tüm diziyi bir grup olarak almanın maliyeti:
        // dp[0] + max(a[1..i]) = 0 + prefix_max[i]
        dp[i] = prefix_max[i];
        
        // Bir diğer aday: son elemanı tek başına ayrı grup yapmak:
        // dp[i-1] + a[i]
        dp[i] = min(dp[i], dp[i-1] + a[i]);
        
        // Şimdi, stack’de tutulan aday partition noktalarını değerlendiriyoruz.
        // Burada stack’in tepesinde, son geçerli adayın indeksi var.
        // Ama yeni gelen a[i] elemanı, bazı adayları “geçecek” (a[i] daha büyük olduğu sürece),
        // çünkü; 
        //   eğer bir aday indeks j için a[j] < a[i] ise,
        //   o zaman, l = j, max(a[j..i]) = a[i] (çünkü a[i] daha büyük),
        //   ve maliyet adayı dp[j-1] + a[i] ile güncellenebilir.
        while(!st.empty() && a[i] >= a[st.back()]){
            int j = st.back();
            st.pop_back();
            // j pozisyonu artık geçerli değil, fakat
            // dp[i] için aday olarak, dp[j-1] + a[i] kullanılabilir.
            dp[i] = min(dp[i], dp[j-1] + a[i]);
        }
        // Eğer stack boş değilse, 
        // stack.back()'daki indeksten sonraki partition noktasında a[st.back()] daha büyük.
        if(!st.empty()){
            int j = st.back();
            // Bu durumda, eğer l = j, 
            // cost = dp[j-1] + max(a[j..i]). Fakat max(a[j..i]) = a[j] (çünkü a[j] > a[i] ve stack sayesinde)
            dp[i] = min(dp[i], dp[j-1] + a[j]);
        }
        // i'yi stack'e ekle
        st.push_back(i);
    }
    
    cout << dp[n] << "\n";
    
    return 0;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 11
• Subtask 5: 0 / 13
• Subtask 6: 0 / 17