/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 540.0 KiB
#2 Accepted 10ms 484.0 KiB
#3 Accepted 364ms 632.0 KiB
#4 Accepted 925ms 880.0 KiB
#5 Memory Exceeded ≥267ms ≥256.016 MiB
#6 Memory Exceeded ≥251ms ≥256.016 MiB

Code

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"
#define F first
#define S second
#define pii pair<int, int>
#define sz(x) (int) (x.size())


// #include<ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// template<typename T> using o_set = tree<T, null_type, std::less<T>, 
// rb_tree_tag, tree_order_statistics_node_update>;

string tmp = "aeiou";
map<char, int> mp;


const int N = 2e5 + 10;
const int mod = 1e9 + 7;
const int INF = 1e18 + 10;


void solve() {
    int n; cin>>n;
    string s; cin>>s;
    mp['a'] = 0;
    mp['e'] = 1;
    mp['i'] = 2;
    mp['o'] = 3;
    mp['u'] = 4;
    vector<vector<vector<int>>> dp(n, vector<vector<int>>(35, vector<int>(6, -1)));

    function<int(int, int, int)> magic = [&] (int ind, int mask, int prv) {
        if(ind == n) {
            return 0LL;
        }


        int &ans = dp[ind][mask][prv];
        if(~ans) return ans;
        ans = INF;

        for(int op = 0; op <= 4; op++) {
            int cur = (mp[s[ind]] + op) % 5, f = (cur != prv);
            if(f && (mask & (1LL << cur))) continue;
            ans = min(ans, op + magic(ind + 1, mask | (1LL << cur), cur));
        }

        // cerr<<"ans: "<<ans<<endl;

        return ans;
    };

    cout<<magic(0, 0, 5)<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1; 
    cin>>t;
    for(int tc = 1; tc <= t; tc++) {
        // cout<<"Case "<<tc<<":";
        solve();
    }
}

Information

Submit By
Type
Submission
Problem
P1140 Vowel arrangement
Contest
LU IUJPC : Sylhet Division 2024
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-09 07:17:34
Judged At
2024-12-09 07:17:34
Judged By
Score
10
Total Time
≥925ms
Peak Memory
≥256.016 MiB