結果
問題 |
No.935 う し た ぷ に き あ く ん 笑 ビ - ム
|
ユーザー |
![]() |
提出日時 | 2019-11-29 22:25:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 638 ms / 2,000 ms |
コード長 | 2,891 bytes |
コンパイル時間 | 1,932 ms |
コンパイル使用メモリ | 182,008 KB |
実行使用メモリ | 66,608 KB |
最終ジャッジ日時 | 2024-09-14 05:49:48 |
合計ジャッジ時間 | 15,038 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 58 |
ソースコード
// #define DEBUGGING #include <bits/stdc++.h> #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template <typename T> using V = std::vector<T>; template <typename T> using VV = V<V<T>>; using ll = std::int64_t; using ull = std::uint64_t; using PLL = std::pair<ll, ll>; using TLL = std::tuple<ll, ll, ll>; template <typename T> const T& var_min(const T &t) { return t; } template <typename T> const T& var_max(const T &t) { return t; } template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); } template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); } template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); } template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; } #define mv_rec make_v(init, tail...) template <typename T> T make_v(T init) { return init; } template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); } #undef mv_rec #ifdef DEBUGGING #include "../../debug/debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif using namespace std; int main() { ll N; cin >> N; string S; cin >> S; V<ll> A(N); for(auto &&ele : A) cin >> ele; V<PLL> result; V<ll> ulis; for(ll i = 0; i < N; i++) { ll enemy = 0; ll used = 0; for(ll j = i; j < N; j++) { enemy += (S[j] == 'E'); used += A[j]; result.emplace_back(enemy, used); ulis.push_back(used); } } { ulis.push_back(0); sort(ALL(ulis)); auto ite = unique(ALL(ulis)); ulis.erase(ite, ulis.end()); } auto get_idx = [&](ll u) { return distance(ulis.begin(), lower_bound(ALL(ulis), u)); }; V<ll> max_v(ulis.size()); for(auto &&ele : result) { ll e, u; tie(e, u) = ele; ll idx = get_idx(u); chmax(max_v[idx], e); } for(ll i = 1; i < max_v.size(); i++) chmax(max_v[i], max_v[i - 1]); ll Q; cin >> Q; while(Q--) { ll a; cin >> a; auto ite = upper_bound(ALL(ulis), a); ite--; ll idx = get_idx(*ite); cout << max_v[idx] << endl; } return 0; }