#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") //#pragma GCC optimize("Ofast") //#undef LOCAL #include #include #include #include #include #include #include #include #include #include namespace yosupo { namespace internal { int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } } // namespace internal int bsf(unsigned int n) { return __builtin_ctz(n); } int bsf(unsigned long n) { return __builtin_ctzl(n); } int bsf(unsigned long long n) { return __builtin_ctzll(n); } int bsf(unsigned __int128 n) { unsigned long long low = (unsigned long long)(n); unsigned long long high = (unsigned long long)(n >> 64); return low ? __builtin_ctzll(low) : 64 + __builtin_ctzll(high); } int bsr(unsigned int n) { return 8 * (int)sizeof(unsigned int) - 1 - __builtin_clz(n); } int bsr(unsigned long n) { return 8 * (int)sizeof(unsigned long) - 1 - __builtin_clzl(n); } int bsr(unsigned long long n) { return 8 * (int)sizeof(unsigned long long) - 1 - __builtin_clzll(n); } int bsr(unsigned __int128 n) { unsigned long long low = (unsigned long long)(n); unsigned long long high = (unsigned long long)(n >> 64); return high ? 127 - __builtin_clzll(high) : 63 - __builtin_ctzll(low); } int popcnt(unsigned int n) { return __builtin_popcount(n); } int popcnt(unsigned long n) { return __builtin_popcountl(n); } int popcnt(unsigned long long n) { return __builtin_popcountll(n); } } // namespace yosupo #include #include #include namespace yosupo { namespace internal { template using is_signed_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using is_unsigned_int128 = typename std::conditional::value || std::is_same::value, std::true_type, std::false_type>::type; template using make_unsigned_int128 = typename std::conditional::value, __uint128_t, unsigned __int128>; template using is_integral = typename std::conditional::value || internal::is_signed_int128::value || internal::is_unsigned_int128::value, std::true_type, std::false_type>::type; template using is_signed_int = typename std::conditional<(is_integral::value && std::is_signed::value) || is_signed_int128::value, std::true_type, std::false_type>::type; template using is_unsigned_int = typename std::conditional<(is_integral::value && std::is_unsigned::value) || is_unsigned_int128::value, std::true_type, std::false_type>::type; template using to_unsigned = typename std::conditional< is_signed_int128::value, make_unsigned_int128, typename std::conditional::value, std::make_unsigned, std::common_type>::type>::type; template using is_integral_t = std::enable_if_t::value>; template using is_signed_int_t = std::enable_if_t::value>; template using is_unsigned_int_t = std::enable_if_t::value>; template using to_unsigned_t = typename to_unsigned::type; } // namespace internal } // namespace yosupo namespace yosupo { struct Scanner { public: Scanner(const Scanner&) = delete; Scanner& operator=(const Scanner&) = delete; Scanner(FILE* fp) : fd(fileno(fp)) { line[0] = 127; } void read() {} template void read(H& h, T&... t) { bool f = read_single(h); assert(f); read(t...); } int read_unsafe() { return 0; } template int read_unsafe(H& h, T&... t) { bool f = read_single(h); if (!f) return 0; return 1 + read_unsafe(t...); } int close() { return ::close(fd); } private: static constexpr int SIZE = 1 << 15; int fd = -1; std::array line; int st = 0, ed = 0; bool eof = false; bool read_single(std::string& ref) { if (!skip_space()) return false; ref = ""; while (true) { char c = top(); if (c <= ' ') break; ref += c; st++; } return true; } bool read_single(double& ref) { std::string s; if (!read_single(s)) return false; ref = std::stod(s); return true; } template ::value>* = nullptr> bool read_single(T& ref) { if (!skip_space<50>()) return false; ref = top(); st++; return true; } template * = nullptr, std::enable_if_t::value>* = nullptr> bool read_single(T& sref) { using U = internal::to_unsigned_t; if (!skip_space<50>()) return false; bool neg = false; if (line[st] == '-') { neg = true; st++; } U ref = 0; do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0'); sref = neg ? -ref : ref; return true; } template * = nullptr, std::enable_if_t::value>* = nullptr> bool read_single(U& ref) { if (!skip_space<50>()) return false; ref = 0; do { ref = 10 * ref + (line[st++] & 0x0f); } while (line[st] >= '0'); return true; } bool reread() { if (ed - st >= 50) return true; if (st > SIZE / 2) { std::memmove(line.data(), line.data() + st, ed - st); ed -= st; st = 0; } if (eof) return false; auto u = ::read(fd, line.data() + ed, SIZE - ed); if (u == 0) { eof = true; line[ed] = '\0'; u = 1; } ed += int(u); line[ed] = char(127); return true; } char top() { if (st == ed) { bool f = reread(); assert(f); } return line[st]; } template bool skip_space() { while (true) { while (line[st] <= ' ') st++; if (ed - st > TOKEN_LEN) return true; if (st > ed) st = ed; for (auto i = st; i < ed; i++) { if (line[i] <= ' ') return true; } if (!reread()) return false; } } }; struct Printer { public: template void write() {} template void write(const H& h, const T&... t) { if (F) write_single(sep); write_single(h); write(t...); } template void writeln(const T&... t) { write(t...); write_single('\n'); } Printer(FILE* _fp) : fd(fileno(_fp)) {} ~Printer() { flush(); } int close() { flush(); return ::close(fd); } void flush() { if (pos) { auto res = ::write(fd, line.data(), pos); assert(res != -1); pos = 0; } } private: static std::array, 100> small; static std::array tens; static constexpr size_t SIZE = 1 << 15; int fd; std::array line; size_t pos = 0; std::stringstream ss; template ::value>* = nullptr> void write_single(const T& val) { if (pos == SIZE) flush(); line[pos++] = val; } template * = nullptr, std::enable_if_t::value>* = nullptr> void write_single(const T& val) { using U = internal::to_unsigned_t; if (val == 0) { write_single('0'); return; } if (pos > SIZE - 50) flush(); U uval = val; if (val < 0) { write_single('-'); uval = -uval; } write_unsigned(uval); } template * = nullptr> void write_single(U uval) { if (uval == 0) { write_single('0'); return; } if (pos > SIZE - 50) flush(); write_unsigned(uval); } template * = nullptr> static int calc_len(U x) { int i = (bsr(x) * 3 + 3) / 10; if (x < tens[i]) return i; else return i + 1; } template * = nullptr, std::enable_if_t<2 >= sizeof(U)>* = nullptr> void write_unsigned(U uval) { size_t len = calc_len(uval); pos += len; char* ptr = line.data() + pos; while (uval >= 100) { ptr -= 2; memcpy(ptr, small[uval % 100].data(), 2); uval /= 100; } if (uval >= 10) { memcpy(ptr - 2, small[uval].data(), 2); } else { *(ptr - 1) = char('0' + uval); } } template * = nullptr, std::enable_if_t<4 == sizeof(U)>* = nullptr> void write_unsigned(U uval) { std::array buf; memcpy(buf.data() + 6, small[uval % 100].data(), 2); memcpy(buf.data() + 4, small[uval / 100 % 100].data(), 2); memcpy(buf.data() + 2, small[uval / 10000 % 100].data(), 2); memcpy(buf.data() + 0, small[uval / 1000000 % 100].data(), 2); if (uval >= 100000000) { if (uval >= 1000000000) { memcpy(line.data() + pos, small[uval / 100000000 % 100].data(), 2); pos += 2; } else { line[pos] = char('0' + uval / 100000000); pos++; } memcpy(line.data() + pos, buf.data(), 8); pos += 8; } else { size_t len = calc_len(uval); memcpy(line.data() + pos, buf.data() + (8 - len), len); pos += len; } } template * = nullptr, std::enable_if_t<8 == sizeof(U)>* = nullptr> void write_unsigned(U uval) { size_t len = calc_len(uval); pos += len; char* ptr = line.data() + pos; while (uval >= 100) { ptr -= 2; memcpy(ptr, small[uval % 100].data(), 2); uval /= 100; } if (uval >= 10) { memcpy(ptr - 2, small[uval].data(), 2); } else { *(ptr - 1) = char('0' + uval); } } template < class U, std::enable_if_t::value>* = nullptr> void write_unsigned(U uval) { static std::array buf; size_t len = 0; while (uval > 0) { buf[len++] = char((uval % 10) + '0'); uval /= 10; } std::reverse(buf.begin(), buf.begin() + len); memcpy(line.data() + pos, buf.data(), len); pos += len; } void write_single(const std::string& s) { for (char c : s) write_single(c); } void write_single(const char* s) { size_t len = strlen(s); for (size_t i = 0; i < len; i++) write_single(s[i]); } template void write_single(const std::vector& val) { auto n = val.size(); for (size_t i = 0; i < n; i++) { if (i) write_single(' '); write_single(val[i]); } } }; std::array, 100> Printer::small = [] { std::array, 100> table; for (int i = 0; i <= 99; i++) { table[i][1] = char('0' + (i % 10)); table[i][0] = char('0' + (i / 10 % 10)); } return table; }(); std::array Printer::tens = [] { std::array table; for (int i = 0; i < 20; i++) { table[i] = 1; for (int j = 0; j < i; j++) { table[i] *= 10; } } return table; }(); } // namespace yosupo using namespace yosupo; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); } template using V = vector; template using VV = V>; #ifdef LOCAL ostream& operator<<(ostream& os, __int128_t x) { if (x < 0) { os << "-"; x *= -1; } if (x == 0) { return os << "0"; } string s; while (x) { s += char(x % 10 + '0'); x /= 10; } reverse(s.begin(), s.end()); return os << s; } ostream& operator<<(ostream& os, __uint128_t x) { if (x == 0) { return os << "0"; } string s; while (x) { s += char(x % 10 + '0'); x /= 10; } reverse(s.begin(), s.end()); return os << s; } template ostream& operator<<(ostream& os, const pair& p); template ostream& operator<<(ostream& os, const V& v); template ostream& operator<<(ostream& os, const deque& v); template ostream& operator<<(ostream& os, const array& a); template ostream& operator<<(ostream& os, const set& s); template ostream& operator<<(ostream& os, const map& m); template ostream& operator<<(ostream& os, const pair& p) { return os << "P(" << p.first << ", " << p.second << ")"; } template ostream& operator<<(ostream& os, const V& v) { os << "["; bool f = false; for (auto d : v) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const deque& v) { os << "["; bool f = false; for (auto d : v) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const array& a) { os << "["; bool f = false; for (auto d : a) { if (f) os << ", "; f = true; os << d; } return os << "]"; } template ostream& operator<<(ostream& os, const set& s) { os << "{"; bool f = false; for (auto d : s) { if (f) os << ", "; f = true; os << d; } return os << "}"; } template ostream& operator<<(ostream& os, const multiset& s) { os << "{"; bool f = false; for (auto d : s) { if (f) os << ", "; f = true; os << d; } return os << "}"; } template ostream& operator<<(ostream& os, const map& s) { os << "{"; bool f = false; for (auto p : s) { if (f) os << ", "; f = true; os << p.first << ": " << p.second; } return os << "}"; } struct PrettyOS { ostream& os; bool first; template auto operator<<(T&& x) { if (!first) os << ", "; first = false; os << x; return *this; } }; template void dbg0(T&&... t) { (PrettyOS{cerr, true} << ... << t); } #define dbg(...) \ do { \ cerr << __LINE__ << " : " << #__VA_ARGS__ << " = "; \ dbg0(__VA_ARGS__); \ cerr << endl; \ } while (false); #else #define dbg(...) #endif Scanner sc = Scanner(stdin); Printer pr = Printer(stdout); V naive(V v, ll t) { int n = int(v.size()); V w(n); w[0] = v[0]; for (ll i = 0; i < t; i++) { ll u = min(w[i % n], v[(i + 1) % n] - w[(i + 1) % n]); w[(i + 1) % n] += u; w[i % n] -= u; } return w; } int main() { int n; sc.read(n); V v(n); for (int i = 0; i < n; i++) { sc.read(v[i]); } ll t; sc.read(t); auto ans = naive(v, t); dbg(ans); return 0; }