#446954 (C++17) No.1012 荷物収集

提出ソース

結果

問題	No.1012 荷物収集
ユーザー	tatyam
提出日時	2020-03-20 22:23:57
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,387 bytes
コンパイル時間	3,394 ms
コンパイル使用メモリ	220,264 KB
実行使用メモリ	18,376 KB
最終ジャッジ日時	2024-12-15 06:40:36
合計ジャッジ時間	60,728 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,640 KB
testcase_01	AC	2 ms 11,428 KB
testcase_02	AC	2 ms 13,636 KB
testcase_03	AC	2 ms 11,428 KB
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	AC	2 ms 13,636 KB
testcase_15	AC	2 ms 11,296 KB
testcase_16	AC	2 ms 13,644 KB
testcase_17	AC	2 ms 11,172 KB
testcase_18	AC	2 ms 11,176 KB
testcase_19	AC	2 ms 11,168 KB
testcase_20	AC	2 ms 13,640 KB
testcase_21	AC	2 ms 6,816 KB
testcase_22	AC	2 ms 6,816 KB
testcase_23	AC	2 ms 6,820 KB
testcase_24	AC	1,791 ms 6,816 KB
testcase_25	TLE	-
testcase_26	AC	690 ms 6,820 KB
testcase_27	AC	35 ms 6,816 KB
testcase_28	TLE	-
testcase_29	AC	125 ms 6,816 KB
testcase_30	TLE	-
testcase_31	AC	89 ms 6,820 KB
testcase_32	AC	359 ms 6,816 KB
testcase_33	AC	638 ms 6,816 KB
testcase_34	AC	587 ms 6,816 KB
testcase_35	TLE	-
testcase_36	AC	181 ms 6,816 KB
testcase_37	AC	210 ms 6,816 KB
testcase_38	TLE	-
testcase_39	AC	434 ms 6,816 KB
testcase_40	AC	620 ms 6,816 KB
testcase_41	TLE	-
testcase_42	AC	888 ms 6,816 KB
testcase_43	AC	1,647 ms 6,816 KB
testcase_44	AC	2 ms 11,300 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
namespace fast {
  // fast I/O by rsk0315 (update: 2019-10-14 16:56:15).
  // This version supports only integer inputs/outputs, single character
  // outputs, and string literal outputs.
  static size_t constexpr buf_size = 1 << 17;
  static size_t constexpr margin = 1;
  static char inbuf[buf_size + margin] = {};
  static char outbuf[buf_size + margin] = {};
  static __attribute__((aligned(8))) char minibuf[32];
  static size_t constexpr int_digits = 20;  // 18446744073709551615
  static uintmax_t constexpr digit_mask = 0x3030303030303030;
  static uintmax_t constexpr first_mask = 0x00FF00FF00FF00FF;
  static uintmax_t constexpr second_mask = 0x0000FFFF0000FFFF;
  static uintmax_t constexpr third_mask = 0x00000000FFFFFFFF;
  static uintmax_t constexpr tenpow[] = {
    1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000
  };
  template <typename Tp>
  using enable_if_integral = std::enable_if<std::is_integral<Tp>::value, Tp>;

  class scanner {
    char* pos = inbuf;
    char* endpos = inbuf + buf_size;

    void M_read_from_stdin() {
      endpos = inbuf + fread(pos, 1, buf_size, stdin);
    }
    void M_reread_from_stdin() {
      ptrdiff_t len = endpos - pos;
      if (!(inbuf + len <= pos)) return;
      memcpy(inbuf, pos, len);
      char* tmp = inbuf + len;
      endpos = tmp + fread(tmp, 1, buf_size-len, stdin);
      *endpos = 0;
      pos = inbuf;
    }

  public:
    scanner() { M_read_from_stdin(); }

    template <typename Integral,
              typename enable_if_integral<Integral>::type* = nullptr>
    void scan_parallel(Integral& x) {
      // See https://qiita.com/rsk0315_h4x/items/17a9cb12e0de5fd918f4
      if (__builtin_expect(endpos <= pos + int_digits, 0))
        M_reread_from_stdin();
      bool ends = false;
      typename std::make_unsigned<Integral>::type y = 0;
      bool neg = false;
      if (std::is_signed<Integral>::value && *pos == '-') {
        neg = true;
        ++pos;
      }
      do {
        memcpy(minibuf, pos, 8);
        long c = *(long*)minibuf;
        long d = (c & digit_mask) ^ digit_mask;
        int skip = 8;
        int shift = 8;
        if (d) {
          int ctz = __builtin_ctzl(d);
          if (ctz == 4) break;
          c &= (1L << (ctz-5)) - 1;
          int discarded = (68-ctz) / 8;
          shift -= discarded;
          c <<= discarded * 8;
          skip -= discarded;
          ends = true;
        }
        c |= digit_mask;
        c ^= digit_mask;
        c = ((c >> 8) + c*10) & first_mask;
        c = ((c >> 16) + c*100) & second_mask;
        c = ((c >> 32) + c*10000) & third_mask;
        y = y*tenpow[shift] + c;
        pos += skip;
      } while (!ends);
      x = (neg? -y: y);
      ++pos;
    }

    template <typename Integral,
              typename enable_if_integral<Integral>::type* = nullptr>
    void scan_serial(Integral& x) {
      if (__builtin_expect(endpos <= pos + int_digits, 0))
        M_reread_from_stdin();
      bool neg = false;
      if (std::is_signed<Integral>::value && *pos == '-') {
        neg = true;
        ++pos;
      }
      typename std::make_unsigned<Integral>::type y = *pos-'0';
      while (*++pos >= '0') y = 10*y + *pos-'0';
      x = (neg? -y: y);
      ++pos;
    }

    template <typename Integral,
              typename enable_if_integral<Integral>::type* = nullptr>
    // Use scan_parallel(x) only when x may be too large (about 10^12).
    // Otherwise, even when x <= 10^9, scan_serial(x) may be faster.
    void scan(Integral& x) { scan_serial(x); }

    void scan_serial(std::string& s) {
      // until first whitespace
      s = "";
      do {
        char* startpos = pos;
        while (*pos > ' ') ++pos;
        s += std::string(startpos, pos);
        if (*pos != 0) {
          ++pos;  // skip the space
          break;
        }
        M_reread_from_stdin();
      } while (true);
    }

    void scan(std::string& s) { scan_serial(s); }
  };

  class printer {
    char* pos = outbuf;

    void M_flush_stdout() {
      fwrite(outbuf, 1, pos-outbuf, stdout);
      pos = outbuf;
    }

  public:
    printer() = default;
    ~printer() { M_flush_stdout(); }

    void print(char c) {
      if (__builtin_expect(pos + 1 >= outbuf + buf_size, 0)) M_flush_stdout();
      *pos++ = c;
    }

    template <size_t N>
    void print(char const(&s)[N]) {
      if (__builtin_expect(pos + N >= outbuf + buf_size, 0)) M_flush_stdout();
      memcpy(pos, s, N-1);
      pos += N-1;
    }

    void print(char const* s) {
      while (*s != 0) {
        *pos++ = *s++;
        if (pos == outbuf + buf_size) M_flush_stdout();
      }
    }

    template <typename Integral,
              typename enable_if_integral<Integral>::type* = nullptr>
    void print(Integral x) {
      if (__builtin_expect(pos + int_digits >= outbuf + buf_size, 0))
        M_flush_stdout();
      if (x == 0) {
        *pos++ = '0';
        return;
      }
      if (x < 0) {
        *pos++ = '-';
        if (__builtin_expect(x == std::numeric_limits<Integral>::min(), 0)) {
          switch (sizeof x) {
          case 2: print("32768"); return;
          case 4: print("2147483648"); return;
          case 8: print("9223372036854775808"); return;
          }
        }
        x = -x;
      }
      char* mp = minibuf + sizeof minibuf;
      *--mp = x % 10 + '0';
      size_t len = 1;
      typename std::make_unsigned<Integral>::type y = x / 10;
      while (y > 0) {
        *--mp = y % 10 + '0';
        y /= 10;
        ++len;
      }
      memcpy(pos, mp, len);
      pos += len;
    }

    template <typename Tp>
    void println(Tp const& x) { print(x), print('\n'); }
  };
}
using uint = unsigned;
using ull = unsigned long long;
inline constexpr uint abs(uint a, uint b){
    if(a > b) return a - b;
    else return b - a;
}
int main(){
    fast::scanner cin;
    fast::printer cout;
    uint n, q;
    cin.scan(n);
    cin.scan(q);
    pair<uint, uint> a[n];
    for(auto& i : a){
        cin.scan(i.first);
        cin.scan(i.second);
    }
    uint x[q];
    for(auto& i : x) cin.scan(i);
    for(int i : x){
        ull ans = 0;
        for(auto& j : a) ans += abs(i, j.first) * ull(j.second);
        cout.println(ans);
    }
}

yukicoder

結果

テストケース

ソースコード