#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include #include #include #include using u32 = uint32_t; using u64 = uint64_t; alignas(64) static u32 S[1000000]; // "12345678" -> 12345678 static inline __attribute__((always_inline)) u32 parse8(u64 x) { x = ((x & 0x0F0F0F0F0F0F0F0FULL) * 2561ULL) >> 8; x = ((x & 0x00FF00FF00FF00FFULL) * 6553601ULL) >> 16; x &= 0x0000FFFF0000FFFFULL; // ここまでで // low = 上4桁 // high = 下4桁 // // 巨大な 64bit multiply を使わずに合成 return (u32)x * 10000u + (u32)(x >> 32); } class FastInput { static constexpr size_t N = 1u << 15; alignas(64) char buf[N + 64]; char* p = buf; char* e = buf; char* lim = buf; char* lim4 = buf; __attribute__((noinline)) void refill() { const size_t rem = (size_t)(e - p); if (rem) { std::memmove(buf, p, rem); } p = buf; e = buf + rem; const size_t want = N - rem; const size_t got = fread_unlocked(e, 1, want, stdin); e += got; if (__builtin_expect(got < want, 0)) { // EOF 付近の先読み用 std::memset(e, 0, 48); lim = e; lim4 = e; } else { lim = e - 16; lim4 = e - 48; } } // バッファ境界チェックなし inline __attribute__((always_inline)) u32 raw() { u64 x; std::memcpy(&x, p, 8); // ASCII 数字は全て bit 4 が立っている。 // ' ' '\n' 等では立っていない。 constexpr u64 DIG = 0x1010101010101010ULL; // 先頭8文字が全部数字 if (__builtin_expect((x & DIG) == DIG, 1)) { u32 v = parse8(x); // A < 10^9 なので // 9文字目が数字なら必ず「9桁」 if (p[8] >= '0') { v = v * 10u + (u32)(p[8] - '0'); // 9桁 + separator p += 10; } else { // 8桁 + separator p += 9; } return v; } // 1~7桁。 // ループを使わず完全展開。 u32 v = (u32)(p[0] - '0'); if (p[1] < '0') { p += 2; return v; } v = v * 10u + (u32)(p[1] - '0'); if (p[2] < '0') { p += 3; return v; } v = v * 10u + (u32)(p[2] - '0'); if (p[3] < '0') { p += 4; return v; } v = v * 10u + (u32)(p[3] - '0'); if (p[4] < '0') { p += 5; return v; } v = v * 10u + (u32)(p[4] - '0'); if (p[5] < '0') { p += 6; return v; } v = v * 10u + (u32)(p[5] - '0'); if (p[6] < '0') { p += 7; return v; } v = v * 10u + (u32)(p[6] - '0'); p += 8; return v; } public: inline __attribute__((always_inline)) u32 next() { if (__builtin_expect(p >= lim, 0)) { refill(); } return raw(); } inline __attribute__((always_inline)) u32 sum4() { // 4個分を読むので境界判定も4回ではなく1回 if (__builtin_expect(p >= lim4, 0)) { refill(); } constexpr u64 DIG = 0x1010101010101010ULL; u64 a, b, c, d; std::memcpy(&a, p, 8); std::memcpy(&b, p + 10, 8); std::memcpy(&c, p + 20, 8); std::memcpy(&d, p + 30, 8); // 4個とも9桁の場合の高速経路。 // // A < 10^9 なので、 // 最初の8文字と9文字目が数字なら // その値は必ずちょうど9桁。 if (__builtin_expect( ((a & b & c & d) & DIG) == DIG && (p[8] & p[18] & p[28] & p[38] & 0x10), 1 )) { u32 s = parse8(a) * 10u + (u32)(p[8] - '0'); s += parse8(b) * 10u + (u32)(p[18] - '0'); s += parse8(c) * 10u + (u32)(p[28] - '0'); s += parse8(d) * 10u + (u32)(p[38] - '0'); p += 40; return s; } // 9桁以外を含んでいても正しく処理 return raw() + raw() + raw() + raw(); } }; // ------------------------------------------------------------ // 出力 // ------------------------------------------------------------ // 0000 ... 9999 を little-endian の u32 として保持 constexpr std::array makeD4() { std::array a{}; for (u32 x = 0; x < 10000; ++x) { u32 v = x; const u32 d3 = v % 10; v /= 10; const u32 d2 = v % 10; v /= 10; const u32 d1 = v % 10; const u32 d0 = v / 10; a[x] = (u32)('0' + d0) | (u32)('0' + d1) << 8 | (u32)('0' + d2) << 16 | (u32)('0' + d3) << 24; } return a; } alignas(64) static constexpr auto D4 = makeD4(); static inline __attribute__((always_inline)) char* put4(char* p, u32 x) { const u32 v = D4[x]; std::memcpy(p, &v, 4); return p + 4; } // 1~4桁。 // D4 の先頭の '0' を shift で捨てる。 static inline __attribute__((always_inline)) char* put1to4(char* p, u32 x) { u32 v = D4[x]; if (x >= 1000u) { std::memcpy(p, &v, 4); return p + 4; } if (x >= 100u) { v >>= 8; // 4 byte 書いても、次の書き込みで上書きされる。 std::memcpy(p, &v, 4); return p + 3; } if (x >= 10u) { v >>= 16; std::memcpy(p, &v, 4); return p + 2; } v >>= 24; std::memcpy(p, &v, 4); return p + 1; } static inline __attribute__((always_inline)) char* putU32(char* p, u32 x) { if (x < 10000u) { return put1to4(p, x); } // base 10000 に分割 const u32 q = x / 10000u; const u32 lo = x - q * 10000u; if (q < 10000u) { p = put1to4(p, q); return put4(p, lo); } const u32 hi = q / 10000u; const u32 mid = q - hi * 10000u; p = put1to4(p, hi); p = put4(p, mid); return put4(p, lo); } class FastOutput { static constexpr size_t N = 1u << 15; alignas(64) char buf[N + 16]; char* p = buf; __attribute__((noinline)) void flush() { fwrite_unlocked( buf, 1, (size_t)(p - buf), stdout ); p = buf; } public: ~FastOutput() { if (p != buf) { flush(); } } inline __attribute__((always_inline)) void write(u32 x) { if (__builtin_expect( p > buf + N - 16, 0 )) { flush(); } p = putU32(p, x); *p++ = '\n'; } }; // ------------------------------------------------------------ int main() { FastInput in; FastOutput out; const u32 H = in.next(); const u32 W = in.next(); u32 T = 0; // H が最大になる領域では W <= 4 なので、 // ここを特別扱いしてループ制御を消す。 if (W == 1) { for (u32 i = 0; i < H; ++i) { const u32 s = in.next(); S[i] = s; T += s; } } else if (W == 2) { for (u32 i = 0; i < H; ++i) { const u32 s = in.next() + in.next(); S[i] = s; T += s; } } else if (W == 3) { for (u32 i = 0; i < H; ++i) { const u32 s = in.next() + in.next() + in.next(); S[i] = s; T += s; } } else if (W == 4) { for (u32 i = 0; i < H; ++i) { const u32 s = in.sum4(); S[i] = s; T += s; } } else { for (u32 i = 0; i < H; ++i) { u32 s = 0; u32 j = 0; for (; j + 4 <= W; j += 4) { s += in.sum4(); } for (; j < W; ++j) { s += in.next(); } S[i] = s; T += s; } } for (u32 i = 0; i < H; ++i) { out.write(S[i] + T); } return 0; }