Submission #533777

#	Time	Username	Problem	Language	Result	Execution time	Memory
533777		tengiz05	Candies (JOI18_candies)	C++17	100 / 100	114 ms	11816 KiB

candies

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    std::priority_queue<std::pair<i64, int>> q;
    
    std::vector<i64> a(n + 2), l(n + 2), r(n + 2);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        q.emplace(a[i], i);
        l[i] = i - 1;
        r[i] = i + 1;
    }
    
    a[0] = a[n + 1] = -1E15;
    
    std::vector<bool> del(n + 2);
    
    i64 ans = 0;
    
    for (int i = 1; i <= (n + 1) / 2; i++) {
        while (del[q.top().second])
            q.pop();
        auto [v, j] = q.top();
        q.pop();
        
        ans += v;
        std::cout << ans << "\n";
        
        del[l[j]] = del[r[j]] = 1;
        a[j] = a[l[j]] + a[r[j]] - a[j];
        
        l[j] = l[l[j]];
        r[j] = r[r[j]];
        r[l[j]] = j;
        l[r[j]] = j;
        
        q.emplace(a[j], j);
    }
    
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92