Submission #34502607

---

Source Code Expand

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f

using i64 = long long;

const int N = 2e5 + 5;

int n;
int a[N];

int main() {

    std::cin >> n;

    for (int i = 0; i < n; i++) std::cin >> a[i];
    for (int i = 0; i < n; i++) a[i + n] = a[i]; 
    std::set<std::pair<int, int>> st;
    for (int i = 0; i < n; i++) {
        st.insert({a[i], i});
    }
    while (true) {
        int u = (*st.begin()).second;
        if ((*st.begin()).first == 0) {
            for (int i = 0; i < n; i++) {
                if (a[i] != 0) {
                    std::cout << "NO" << '\n';
                    return 0; 
                } 
            }
            std::cout << "YES" << '\n';
            return 0; 
        }
        int k = inf; 
        for (int i = u; i < u + n; i++) {
            k = std::min(k, a[i] / (i - u + 1));
        }
        if (k == 0) {
            std::cout << "NO" << '\n';
            return 0; 
        }
        for (int i = u; i < u + n; i++) {
            st.erase({a[i], i % n}), st.erase({a[i], i % n + n}); 
            a[i % n] -= k * (i - u + 1), a[i % n + n] -= k * (i - u + 1); 
            st.insert({a[i], i % n}), st.insert({a[i], i % n + n});
        }
    }
    return 0; 
}

Submission Info

Judge Result