結果

問題 No.1433 Two color sequence
ユーザー CyanmondCyanmond
提出日時 2021-03-19 22:18:06
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 5,021 bytes
コンパイル時間 6,110 ms
コンパイル使用メモリ 302,464 KB
実行使用メモリ 6,740 KB
最終ジャッジ日時 2023-08-12 02:40:39
合計ジャッジ時間 8,112 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 16 ms
6,708 KB
testcase_04 AC 16 ms
6,696 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 30 ms
6,740 KB
testcase_09 AC 31 ms
6,660 KB
testcase_10 AC 30 ms
6,448 KB
testcase_11 AC 31 ms
6,396 KB
testcase_12 AC 31 ms
6,728 KB
testcase_13 AC 31 ms
6,720 KB
testcase_14 AC 31 ms
6,696 KB
testcase_15 AC 31 ms
6,676 KB
testcase_16 AC 30 ms
6,656 KB
testcase_17 AC 30 ms
6,660 KB
testcase_18 AC 30 ms
6,672 KB
testcase_19 AC 30 ms
6,676 KB
testcase_20 AC 30 ms
6,672 KB
testcase_21 AC 31 ms
6,676 KB
testcase_22 AC 31 ms
6,700 KB
testcase_23 AC 30 ms
6,704 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region library
#if defined(__GNUC__) && !defined(__llvm__) && !defined(__clang__)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#endif
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif
#pragma region
#define whole(f, x, ...) ([&](auto& v) { return (f)(std::begin(v), std::end(v), ## __VA_ARGS__); })(x)

#define rep32(i, l, r) for (int i = (int)(l); (i) < (int)(r); ++(i))
#define rep64(i, l, r) for (long long i = (long long)(l); i < (long long)(r); ++(i))
#define revrep32(i, r, l) for (int i = (int)(r); (i) >= (int)(l); --(i))
#define revrep64(i, r, l) for (long long i = (long long)(r); i >= (long long)(l); --(i))

using u32 = unsigned int;
using usize = size_t;
using index_t = size_t;
using i64 = long long;
using u64 = unsigned long long;
constexpr size_t operator "" _uz(unsigned long long v) { return static_cast<size_t>(v); }

template <class T> using Heap = std::priority_queue<T>;
template <class T> using RevHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template <class T, class F> using SHeap = std::priority_queue<T, std::vector<T>, F>;

constexpr int dx[] = { 1, 0, -1, 0 };
constexpr int dy[] = { 0, 1, 0, -1 };

constexpr int INF32 = 1001001001;
constexpr long long INF64 = 1501501501501501501ll;

constexpr int mod = 1000000007;
constexpr int mod2 = 998244353;

#pragma endregion

template <class T, class U>
constexpr bool chmin(T& a, const U& b) noexcept {
  return a > b ? a = b, true : false;
}
template <class T, class U>
constexpr bool chmax(T& a, const U& b) noexcept {
  return a < b ? a = b, true : false;
}
template <class type = size_t, class T> constexpr type len(const T& v) noexcept { return (type)(v.size()); }

template <class T, class... Ts> std::vector<std::tuple<T&, Ts&...>> zip(std::vector<T>& t, std::vector<Ts>&... ts) {
  const size_t n = t.size();
  std::vector<std::tuple<T&, Ts&...>> res;
  for (size_t i = 0; i < n; i++) res.emplace_back(t[i], ts[i]...);
  return res;
}
template <class T, class... Ts> std::vector<std::tuple<size_t, T&, Ts&...>> idzip(std::vector<T>& t, std::vector<Ts>&... ts) {
  const size_t n = t.size();
  std::vector<std::tuple<size_t, T&, Ts&...>> res;
  for (size_t i = 0; i < n; i++) res.emplace_back(i, t[i], ts[i]...);
  return res;
}

namespace nlb {
  template <class T, class U> constexpr T Pow(T A, U B) noexcept {
    T res = 1;
    while (B) {
      if (B & 1) { res *= A; }
      A *= A; B >>= 1;
    }
    return res;
  }

  template <class T, class U, class M = int> constexpr T modpow(T A, U B, M MOD = 1000000007) noexcept {
    A %= MOD;
    T res = 1;
    while (B) {
      if (B & 1) { res *= A; res %= MOD; }
      A *= A; A %= MOD;
      B >>= 1;
    }
    return res;
  }

  template <class T, class M = int> constexpr T inverse(T A, const M MOD = 1000000007) noexcept {
    T B = MOD, U = 1, V = 0;
    while (B) {
      T t = A / B;
      A -= t * B; std::swap(A, B);
      U -= t * V; std::swap(U, V);
    }
    U %= MOD;
    return U < 0 ? U += MOD, U : U;
  }

  template <class T> constexpr bool isprime(const T N) noexcept {
    if (N == 1) return false;
    for (T i = 2; i * i <= N; i++) if (N % i == 0) return false;
    return true;
  }

  inline std::tuple<long long, long long, long long> extgcd(const long long a, const long long b) {
    if (b == 0) return { a,1,0 };
    long long g, x, y;
    std::tie(g, x, y) = extgcd(b, a % b);
    return std::make_tuple(g, y, x - a / b * y);
  }

  inline std::pair<long long, long long> Chinese_Rem(const std::vector<long long>& b, const std::vector<long long>& m) {
    long long r = 0, M = 1;
    for (int i = 0; i < (int)b.size(); ++i) {
      long long p, q, d;
      std::tie(d, p, q) = extgcd(M, m[i]);
      if ((b[i] - r) % d != 0) return std::make_pair(0, -1);
      long long tmp = (b[i] - r) / d * p % (m[i] / d);
      r += M * tmp;
      M *= m[i] / d;
    }
    return std::make_pair((r % M + M) % M, M);
  }
}

class ProCon_all_init {
  static constexpr bool float_fixed = true;
  static constexpr int ios_perc = 15;
  static constexpr bool ios_fast = true;
  static constexpr bool auto_flush = false;
public:
  ProCon_all_init() {
    if (ios_fast) { std::cin.tie(nullptr); std::cout.tie(nullptr); std::ios::sync_with_stdio(false); }
    if (float_fixed) { std::cout << std::fixed << std::setprecision(ios_perc); }
    if (auto_flush) { std::cout << std::unitbuf; }
  }
} ProCon_;
#pragma endregion

int main(void) {
  int N; std::cin >> N;
  std::string S; std::cin >> S;
  std::vector<i64> A(N);
  for (auto& el : A) std::cin >> el;
  std::vector<i64> R(N + 1);
  R[0] = 0;
  rep32(i, 0, N) {
    // A のここまでの総和 - Bのここまでの総和
    R[i + 1] = R[i] + (S[i] == 'R' ? A[i] : -A[i]);
  }
  i64 Answer = 0;
  i64 min = 0, max = 0;
  rep32(i, 1, N + 1) {
    chmin(min, R[i]);
    chmax(max, R[i]);
    chmax(Answer, std::abs(R[i] - min));
    chmax(Answer, std::abs(R[i] - max));
  }
  std::cout << Answer << std::endl;
}
0