QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#30537#2465. Where Have You Bin?sinbad#AC ✓39ms3756kbC++175.4kb2022-04-29 22:13:352022-04-29 22:13:36

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 22:13:36]
  • 评测
  • 测评结果:AC
  • 用时:39ms
  • 内存:3756kb
  • [2022-04-29 22:13:35]
  • 提交

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'