QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#30537 | #2465. Where Have You Bin? | sinbad# | AC ✓ | 39ms | 3756kb | C++17 | 5.4kb | 2022-04-29 22:13:35 | 2022-04-29 22:13:36 |
Judging History
answer
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>
using namespace std;
template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
out << "(" << a.first << "," << a.second << ")";
return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
out << "["; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << ": " << arg1 << " |";
__f(comma + 1, args...);
}
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
// mt19937 mrand(random_device{}());
// int rnd(int x) { return mrand() % x; }
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
int lg2(int64 x) { return sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
struct fast_ios {
fast_ios() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
};
} fast_ios_;
int main() {
string s;
cin >> s;
int n = SZ(s);
vector<int> w(n);
for (int i = 0; i < n; ++i) cin >> w[i];
string company = "AEIOU";
vector<int> a(n), cnt(5), sum(5);
for (int i = 0; i < n; ++i) {
if (s[i] == 'X') {
a[i] = -1;
} else {
a[i] = company.find(s[i]);
sum[a[i]] += w[i];
cnt[a[i]]++;
}
}
int m;
cin >> m;
while (m--) {
int x;
cin >> x;
--x;
if (a[x] != -1) {
sum[a[x]] -= w[x];
cnt[a[x]]--;
a[x] = -1;
}
}
cin >> s;
if (s != "X") {
for (auto& c : s) cnt[company.find(c)]++;
}
int ret = inf<int>;
vector<int> p(5);
iota(p.begin(), p.end(), 0);
do {
// trace(p, a, cnt, sum);
auto dp = vect<int>(-1, n, 5);
function<int(int, int)> solve =
[&](int pos, int stage) {
if (stage == 5) return 0;
if (pos == n) return inf<int>;
int& ret = dp[pos][stage];
if (ret >= 0) return ret;
ret = inf<int>;
int k = p[stage], cost = sum[k];
for (int i = pos; i + cnt[k] <= n; ++i) {
if (i == pos) {
for (int j = 0; j < cnt[k]; ++j) {
if (a[i + j] == k) cost -= w[i + j];
}
} else {
if (a[i - 1] == k) cost += w[i - 1];
if (a[i + cnt[k] - 1] == k) cost -= w[i + cnt[k] - 1];
}
// trace(stage, k, cost, pos, cnt[k], n);
int cur = cost + solve(i + cnt[k], stage + 1);
ckmin(ret, cur);
}
return ret;
};
int cur = solve(0, 0);
ckmin(ret, cur);
// break;
} while (next_permutation(p.begin(), p.end()));
cout << ret << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3756kb
input:
AEIOUU 1 4 6 9 2 3 1 6 A
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3576kb
input:
AEIOUU 10 4 6 9 2 3 1 6 A
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 3ms
memory: 3716kb
input:
AEIOUU 1 4 6 9 2 3 4 5 1 4 3 EUE
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
A 100 0 X
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
A 100 1 1 X
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 3ms
memory: 3524kb
input:
A 100 1 1 A
output:
0
result:
ok single line: '0'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
A 100 1 1 U
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
X 0 0 X
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
X 0 0 E
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 3ms
memory: 3668kb
input:
AAEIOU 10 10 9 10 8 7 1 1 I
output:
8
result:
ok single line: '8'
Test #11:
score: 0
Accepted
time: 3ms
memory: 3524kb
input:
AAEIOU 10 10 8 10 9 7 1 1 I
output:
8
result:
ok single line: '8'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
AAEIOU 3 3 8 3 9 7 1 1 I
output:
6
result:
ok single line: '6'
Test #13:
score: 0
Accepted
time: 21ms
memory: 3732kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 16 37 4...
output:
1519
result:
ok single line: '1519'
Test #14:
score: 0
Accepted
time: 11ms
memory: 3724kb
input:
AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...
output:
933
result:
ok single line: '933'
Test #15:
score: 0
Accepted
time: 16ms
memory: 3732kb
input:
AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...
output:
741
result:
ok single line: '741'
Test #16:
score: 0
Accepted
time: 14ms
memory: 3528kb
input:
AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...
output:
421
result:
ok single line: '421'
Test #17:
score: 0
Accepted
time: 15ms
memory: 3560kb
input:
AAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 16 37 44 20 5 42 100 100 49 100 33 28 54 60 12 7 31 43 20 87 46 60 83 1 98 86 54 100 8 100 11 46 12 94 39 90 17 ...
output:
261
result:
ok single line: '261'
Test #18:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
AAEEIIOOUUX 1 1 30 100 30 100 30 100 30 100 0 0 A
output:
120
result:
ok single line: '120'
Test #19:
score: 0
Accepted
time: 3ms
memory: 3588kb
input:
AAEEIIOOUUXX 1 1 30 100 30 100 30 100 30 100 0 0 0 A
output:
120
result:
ok single line: '120'
Test #20:
score: 0
Accepted
time: 3ms
memory: 3732kb
input:
AAEEIIOOUUXXX 1 1 30 100 30 100 30 100 30 100 0 0 0 0 A
output:
2
result:
ok single line: '2'
Test #21:
score: 0
Accepted
time: 3ms
memory: 3664kb
input:
AEIOUUUUUUU 11 1 2 3 4 5 6 7 8 9 10 3 6 8 10 AAA
output:
16
result:
ok single line: '16'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
UUUUUUUOIEA 10 9 8 7 6 5 4 3 2 1 11 3 2 4 6 AAA
output:
16
result:
ok single line: '16'
Test #23:
score: 0
Accepted
time: 23ms
memory: 3676kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 88 3 76 58 50 93 70 83 83 100 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 16 37 4...
output:
1739
result:
ok single line: '1739'
Test #24:
score: 0
Accepted
time: 22ms
memory: 3636kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 31 6 3 43 1 89 91 65 84 81 88 3 76 58 100 93 99 83 100 54 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 100 37 ...
output:
1668
result:
ok single line: '1668'
Test #25:
score: 0
Accepted
time: 34ms
memory: 3748kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 26 3 76 58 50 93 70 99 83 100 66 2 85 68 43 74 90 61 1 88 60 1 92 71 83 33 79 85 6 9 16 37 4...
output:
495
result:
ok single line: '495'
Test #26:
score: 0
Accepted
time: 39ms
memory: 3588kb
input:
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAEEEEEEEEEEEEEEEEEEEEEEEEEEEEEEIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 31 6 3 43 100 89 91 65 84 81 26 3 76 58 50 93 70 99 83 99 66 2 85 68 43 74 90 61 1 88 60 1 92 71 100 33 79 85 6 9 16 37 ...
output:
495
result:
ok single line: '495'
Test #27:
score: 0
Accepted
time: 38ms
memory: 3636kb
input:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0
result:
ok single line: '0'
Test #28:
score: 0
Accepted
time: 9ms
memory: 3660kb
input:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 20ms
memory: 3584kb
input:
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...
output:
0
result:
ok single line: '0'
Test #30:
score: 0
Accepted
time: 4ms
memory: 3520kb
input:
AAAAAAAAAAAAAAAAAAEEEEEEIIIIIIIIIIIOOOOUUUUUUUUUUU 20 56 55 39 45 2 15 81 42 49 31 6 3 43 42 89 91 65 84 81 88 3 76 58 50 93 70 83 83 54 66 2 85 68 43 74 90 61 1 26 60 1 92 71 83 33 79 85 6 9 39 11 39 7 24 44 34 20 23 25 29 49 31 17 37 45 22 9 18 14 2 41 35 16 36 26 13 40 5 43 42 28 21 48 8 19 12 38...
output:
0
result:
ok single line: '0'
Test #31:
score: 0
Accepted
time: 4ms
memory: 3520kb
input:
AAAAAAAAAAAXXXEEEEEEEEEXXXXIIIXXXOOOOOOOOOUUUUUXXX 14 84 66 62 55 24 5 67 22 97 59 0 0 0 86 67 61 71 86 22 98 4 42 0 0 0 0 13 77 70 0 0 0 60 81 94 68 69 40 71 13 5 55 30 74 99 60 0 0 0 21 35 6 36 11 39 38 8 34 2 22 21 16 15 40 47 18 7 44 4 3 37 OAEEAOUUUOUEIEUUAAOUUOEIEOIEOUOIOO
output:
206
result:
ok single line: '206'
Test #32:
score: 0
Accepted
time: 4ms
memory: 3716kb
input:
AAAAAAAAAEEEEEEEEEEEEIIIIIIIIIXXOOOOOOOOOOOOUUUUUU 16 37 44 20 5 42 100 56 49 96 33 28 54 60 12 7 31 43 20 87 81 74 99 74 98 42 4 52 86 73 0 0 5 83 1 98 86 54 85 8 11 46 12 94 39 90 17 37 18 64 32 21 20 35 41 13 12 7 40 26 39 6 45 47 15 2 25 19 34 3 27 29 11 49 1 33 36 23 38 5 46 8 43 AEIEIIOUUEAAUA...
output:
256
result:
ok single line: '256'
Test #33:
score: 0
Accepted
time: 2ms
memory: 3532kb
input:
AAAAAAAXEEEEEXXXXIIIIIIIIIOOOOOOOOOOUUUUUUUUUUUXXX 86 19 11 62 35 80 45 0 4 22 92 62 88 0 0 0 0 80 53 74 32 6 35 33 20 53 99 34 51 58 98 94 52 35 52 90 87 16 93 45 72 51 12 33 68 16 67 0 0 0 18 6 9 37 39 23 22 40 18 29 12 32 1 31 43 4 38 3 30 AIOAUOUIAU
output:
155
result:
ok single line: '155'
Test #34:
score: 0
Accepted
time: 4ms
memory: 3576kb
input:
AAAAAAAAAXXXEEEXXIIIIIIIIIIIIIXOOOOOOOOOOOUUUUUUUX 80 30 91 15 14 98 86 12 38 0 0 0 41 20 57 0 0 86 72 39 37 11 20 3 27 84 66 34 89 77 0 64 93 1 22 58 95 17 30 92 41 10 80 69 96 58 63 6 1 0 4 32 22 27 5 IOIUIUEA
output:
10
result:
ok single line: '10'
Test #35:
score: 0
Accepted
time: 4ms
memory: 3592kb
input:
AAAAAAAXXEEEEEEEEEEEEIIIIIIIIXXXXXOOOOOOOOUUUUUXXX 58 40 59 87 43 68 61 0 0 71 43 46 76 54 64 94 31 48 21 12 80 18 62 77 69 84 66 39 7 0 0 0 0 0 67 68 10 36 19 23 55 38 93 88 3 56 3 0 0 0 6 28 4 43 14 6 27 EEIIU
output:
61
result:
ok single line: '61'