結果
問題 | No.935 う し た ぷ に き あ く ん 笑 ビ - ム |
ユーザー |
![]() |
提出日時 | 2019-11-29 22:06:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 6 ms / 2,000 ms |
コード長 | 1,614 bytes |
コンパイル時間 | 1,734 ms |
コンパイル使用メモリ | 173,256 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-14 05:43:13 |
合計ジャッジ時間 | 3,351 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 58 |
ソースコード
#include <bits/stdc++.h> using namespace std; string to_string(string s) { return '"' + s + '"'; } string to_string(bool b) { return b ? "true" : "false"; } template <class T, class U> string to_string(pair<T, U> p); template <class C> string to_string(C c) { string res = "{"; for (auto e : c) res += to_string(e) + ", "; return res += "}"; } template <size_t N> string to_string(bitset<N> bs) { string res; for (size_t i = 0; i < N; ++i) res += '0' + bs[i]; return res; } template <class T, class U> string to_string(pair<T, U> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } void debug() { cerr << '\n'; } template <class Head, class... Tail> void debug(Head head, Tail... tail) { cerr << ' ' << to_string(head), debug(tail...); } #ifdef LOCAL #define DEBUG(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__) #else #define DEBUG(...) #endif int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin >> n; string s; cin >> s; vector<long long> a(n); for (auto&& e : a) { cin >> e; } a.push_back(0); for (int i = n - 1; i >= 0; --i) { a[i] += a[i + 1]; } vector<int> c(n + 1); for (int i = n - 1; i >= 0; --i) { c[i] = (s[i] == 'E') + c[i + 1]; } vector<long long> mn(n + 1, 1e18); for (int r = 0; r <= n; ++r) { for (int l = 0; l <= r; ++l) { int x = c[l] - c[r]; mn[x] = min(mn[x], a[l] - a[r]); } } DEBUG(mn); int q; cin >> q; while (q--) { int k; cin >> k; int res = prev(upper_bound(begin(mn), end(mn), k)) - begin(mn); cout << res << '\n'; } }