#948481 (C++23) No.2601 Very Poor

提出ソース

結果

問題	No.2601 Very Poor
ユーザー	Re0denX
提出日時	2024-02-07 00:00:11
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	34 ms / 2,000 ms
コード長	5,714 bytes
コンパイル時間	2,655 ms
コンパイル使用メモリ	253,096 KB
実行使用メモリ	9,624 KB
最終ジャッジ日時	2024-09-30 06:41:56
合計ジャッジ時間	4,367 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 KB
testcase_03	AC	2 ms 6,820 KB
testcase_04	AC	2 ms 6,820 KB
testcase_05	AC	2 ms 6,820 KB
testcase_06	AC	2 ms 6,820 KB
testcase_07	AC	2 ms 6,820 KB
testcase_08	AC	2 ms 6,816 KB
testcase_09	AC	2 ms 6,816 KB
testcase_10	AC	2 ms 6,816 KB
testcase_11	AC	2 ms 6,816 KB
testcase_12	AC	2 ms 6,816 KB
testcase_13	AC	2 ms 6,816 KB
testcase_14	AC	2 ms 6,820 KB
testcase_15	AC	21 ms 9,532 KB
testcase_16	AC	27 ms 9,596 KB
testcase_17	AC	22 ms 9,580 KB
testcase_18	AC	15 ms 9,616 KB
testcase_19	AC	16 ms 9,588 KB
testcase_20	AC	14 ms 9,472 KB
testcase_21	AC	24 ms 9,476 KB
testcase_22	AC	20 ms 9,588 KB
testcase_23	AC	22 ms 9,544 KB
testcase_24	AC	34 ms 9,600 KB
testcase_25	AC	27 ms 9,552 KB
testcase_26	AC	16 ms 9,584 KB
testcase_27	AC	22 ms 9,576 KB
testcase_28	AC	23 ms 9,600 KB
testcase_29	AC	30 ms 9,600 KB
testcase_30	AC	25 ms 9,624 KB
testcase_31	AC	18 ms 9,596 KB
testcase_32	AC	24 ms 9,600 KB
testcase_33	AC	23 ms 9,548 KB
testcase_34	AC	10 ms 9,540 KB
testcase_35	AC	2 ms 6,816 KB
testcase_36	AC	2 ms 6,816 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>

using namespace std;
#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif  // LOCAL

struct ChronoTimer {
  std::chrono::high_resolution_clock::time_point st;

  ChronoTimer() { reset(); }

  void reset() { st = std::chrono::high_resolution_clock::now(); }

  std::chrono::milliseconds::rep elapsed() {
    auto ed = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::milliseconds>(ed - st)
        .count();
  }
};

/**
 * @brief Scanner(高速入力)
 */
struct Scanner {
 public:
  explicit Scanner(FILE *fp) : fp(fp) {}

  template <typename T, typename... E>
  void read(T &t, E &...e) {
    read_single(t);
    read(e...);
  }

 private:
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  FILE *fp = nullptr;
  char *st = line;
  char *ed = line;

  void read() {}

  static inline bool is_space(char c) { return c <= ' '; }

  void reread() {
    ptrdiff_t len = ed - st;
    memmove(line, st, len);
    char *tmp = line + len;
    ed = tmp + fread(tmp, 1, line_size - len, fp);
    *ed = 0;
    st = line;
  }

  void skip_space() {
    while (true) {
      if (st == ed) reread();
      while (*st && is_space(*st)) ++st;
      if (st != ed) return;
    }
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void read_single(T &s) {
    skip_space();
    if (st + int_digits >= ed) reread();
    bool neg = false;
    if (is_signed<T>::value && *st == '-') {
      neg = true;
      ++st;
    }
    typename make_unsigned<T>::type y = *st++ - '0';
    while (*st >= '0') {
      y = 10 * y + *st++ - '0';
    }
    s = (neg ? -y : y);
  }

  template <typename T, enable_if_t<is_same<T, string>::value, int> = 0>
  void read_single(T &s) {
    s = "";
    skip_space();
    while (true) {
      char *base = st;
      while (*st && !is_space(*st)) ++st;
      s += string(base, st);
      if (st != ed) return;
      reread();
    }
  }

  template <typename T>
  void read_single(vector<T> &s) {
    for (auto &d : s) read(d);
  }
};

/**
 * @brief Printer(高速出力)
 */
struct Printer {
 public:
  explicit Printer(FILE *fp) : fp(fp) {}

  ~Printer() { flush(); }

  template <bool f = false, typename T, typename... E>
  void write(const T &t, const E &...e) {
    if (f) write_single(' ');
    write_single(t);
    write<true>(e...);
  }

  template <typename... T>
  void writeln(const T &...t) {
    write(t...);
    write_single('\n');
  }

  void flush() {
    fwrite(line, 1, st - line, fp);
    st = line;
  }

 private:
  FILE *fp = nullptr;
  static constexpr size_t line_size = 1 << 16;
  static constexpr size_t int_digits = 20;
  char line[line_size + 1] = {};
  char *st = line;

  template <bool f = false>
  void write() {}

  void write_single(const char &t) {
    if (st + 1 >= line + line_size) flush();
    *st++ = t;
  }

  template <typename T, enable_if_t<is_integral<T>::value, int> = 0>
  void write_single(T s) {
    if (st + int_digits >= line + line_size) flush();
    st += to_chars(st, st + int_digits, s).ptr - st;
  }

  void write_single(const string &s) {
    for (auto &c : s) write_single(c);
  }

  void write_single(const char *s) {
    while (*s != 0) write_single(*s++);
  }

  template <typename T>
  void write_single(const vector<T> &s) {
    for (size_t i = 0; i < s.size(); i++) {
      if (i) write_single(' ');
      write_single(s[i]);
    }
  }
};

Scanner scanner = Scanner(stdin);
Printer printer = Printer(stdout);

void flush() { printer.flush(); }
void print() { printer.write('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&...tail) {
  printer.write(head);
  if (sizeof...(Tail)) printer.write(' ');
  print(forward<Tail>(tail)...);
}

void read() {}
template <class Head, class... Tail>
void read(Head &head, Tail &...tail) {
  scanner.read(head);
  read(tail...);
}
#define INT(...)   \
  int __VA_ARGS__; \
  read(__VA_ARGS__)
#define LL(...)   \
  long long __VA_ARGS__; \
  read(__VA_ARGS__)
#define STR(...)      \
  string __VA_ARGS__; \
  read(__VA_ARGS__)
#define CHAR(...)   \
  char __VA_ARGS__; \
  read(__VA_ARGS__)
#define DBL(...)      \
  double __VA_ARGS__; \
  read(__VA_ARGS__)

#define VEC(type, name, size) \
  vector<type> name(size);    \
  read(name)
#define VV(type, name, h, w)                     \
  vector<vector<type>> name(h, vector<type>(w)); \
  read(name)

int main(int, char **) {
#ifdef LOCAL
  ChronoTimer chrono;
  freopen("/home/user/acm/competitve/src/input.txt", "r", stdin);
  freopen("/home/user/acm/competitve/src/output.txt", "w", stdout);
#endif
  std::cout << fixed << setprecision(12);

  INT(N, X);
  VEC(long long, A, N);

  long long ret = std::accumulate(A.begin(), A.end(), 0LL);
  A.resize(N * 2);
  std::vector<long long> S(N * 2 + 1);
  for (auto i : views::iota(0, N)) {
    A[i + N] = A[i];
  }

  for (auto i : views::iota(0, N * 2)) {
    S[i + 1] = S[i] + A[i];
  }

  debug(A);
  debug(S);
  int lo = 0, hi = std::min<int>(ret, X);
  int ans = 0;

  auto check = [&] (long long x) -> bool {
    for (auto i : views::iota(1, N + 1)) {
      int dif = std::distance(S.begin() + i, std::lower_bound(S.begin() + i, S.end(), S[i - 1] + x));
      if (dif > N) continue;
      if (S[dif + i] - S[i - 1] < x) continue;
      if (S[dif + i] - S[i - 1] > X) continue;
      debug(i, dif, x);
      return true;
    }

    return false;
  };

  while (lo <= hi) {
    long long x = (lo + hi) / 2;
    if (check(x)) {
      lo = x + 1;
      ans = x;
    } else {
      hi = x - 1;
    }
  }

  print(ans);

#ifdef LOCAL
  print("\nRunning Time:", chrono.elapsed(), "ms");
#endif
}

yukicoder

結果

テストケース

ソースコード