結果
問題 | No.935 う し た ぷ に き あ く ん 笑 ビ - ム |
ユーザー |
|
提出日時 | 2019-11-29 21:57:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,135 bytes |
コンパイル時間 | 2,485 ms |
コンパイル使用メモリ | 204,888 KB |
最終ジャッジ日時 | 2025-01-08 05:54:24 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 54 TLE * 4 |
ソースコード
#include <bits/stdc++.h> // created [2019/11/29] 21:47:35 #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" using i32 = int32_t; using i64 = int64_t; using u32 = uint32_t; using u64 = uint64_t; using uint = unsigned int; using usize = std::size_t; using ll = long long; using ull = unsigned long long; using ld = long double; template<typename T> constexpr T popcount(const T u) { return u ? static_cast<T>(__builtin_popcountll(static_cast<u64>(u))) : static_cast<T>(0); } template<typename T> constexpr T log2p1(const T u) { return u ? static_cast<T>(64 - __builtin_clzll(static_cast<u64>(u))) : static_cast<T>(0); } template<typename T> constexpr T msbp1(const T u) { return log2p1(u); } template<typename T> constexpr T lsbp1(const T u) { return __builtin_ffsll(u); } template<typename T> constexpr T clog(const T u) { return u ? log2p1(u - 1) : static_cast<T>(u); } template<typename T> constexpr bool ispow2(const T u) { return u and (static_cast<u64>(u) & static_cast<u64>(u - 1)) == 0; } template<typename T> constexpr T ceil2(const T u) { return static_cast<T>(1) << clog(u); } template<typename T> constexpr T floor2(const T u) { return u == 0 ? static_cast<T>(0) : static_cast<T>(1) << (log2p1(u) - 1); } template<typename T> constexpr bool btest(const T mask, const usize ind) { return static_cast<bool>((static_cast<u64>(mask) >> ind) & static_cast<u64>(1)); } template<typename T> void bset(T& mask, const usize ind) { mask |= (static_cast<T>(1) << ind); } template<typename T> void breset(T& mask, const usize ind) { mask &= ~(static_cast<T>(1) << ind); } template<typename T> void bflip(T& mask, const usize ind) { mask ^= (static_cast<T>(1) << ind); } template<typename T> void bset(T& mask, const usize ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); } template<typename T> constexpr T bcut(const T mask, const usize ind) { return ind == 0 ? static_cast<T>(0) : static_cast<T>((static_cast<u64>(mask) << (64 - ind)) >> (64 - ind)); } template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); } template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); } constexpr unsigned int mod = 1000000007; template<typename T> constexpr T inf_v = std::numeric_limits<T>::max() / 4; template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884}; template<typename T> T read() { T v; return std::cin >> v, v; } template<typename T, typename... Args> auto read(const usize size, Args... args) { std::vector<decltype(read<T>(args...))> ans(size); for (usize i = 0; i < size; i++) { ans[i] = read<T>(args...); } return ans; } template<typename... Types> auto reads() { return std::tuple<std::decay_t<Types>...>{read<Types>()...}; } # define SHOW(...) static_cast<void>(0) template<typename T> std::vector<T> make_v(const usize size, const T v) { return std::vector<T>(size, v); } template<typename... Args> auto make_v(const usize size, Args... args) { return std::vector<decltype(make_v(args...))>(size, make_v(args...)); } int main() { const int N = read<int>(); const auto S = read<std::string>(); std::vector<int> en(N, 0); for (int i = 0; i < N; i++) { en[i] = (i == 0 ? 0 : en[i - 1]) + (S[i] == 'E'); } auto enemy = [&](const int i, const int j) { return en[j - 1] - (i == 0 ? 0 : en[i - 1]); }; auto A = read<ll>(N); for (int i = 1; i < N; i++) { A[i] += A[i - 1]; } auto energy = [&](const int i, const int j) { return A[j - 1] - (i == 0 ? 0 : A[i - 1]); }; std::map<ll, int> mp; mp[0] = 0; for (int i = 0; i < N; i++) { for (int j = i + 1; j <= N; j++) { chmax(mp[energy(i, j)], enemy(i, j)); } } int max = 0; for (auto& e : mp) { chmax(max, e.second); e.second = max; } SHOW(mp); const int Q = read<int>(); for (int q = 0; q < Q; q++) { const ll K = read<ll>(); const auto it = std::prev(mp.upper_bound(K)); std::cout << it->second << std::endl; } return 0; }