/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 328.0 KiB
#2 Accepted 12ms 860.0 KiB
#3 Accepted 389ms 768.0 KiB
#4 Accepted 1175ms 748.0 KiB
#5 Time Exceeded ≥1603ms ≥186.254 MiB
#6 Time Exceeded ≥1609ms ≥186.191 MiB

Code

/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define life_is_a_race ios::sync_with_stdio(false); cin.tie(nullptr);
//map<pair<char,char>,int> tc;
unordered_map<char,int> indx;
string aeiou = "aeiou",s;
int n,tc[26][26];

int rec(int i,int mask,int last,vector<vector<vector<int>>>&dp)
{
    if(i==n) return 0;
    if(dp[i][mask][last] != -1) return dp[i][mask][last];
    int x = 10000000;
    x = min(x,(aeiou[last]=='a' || (mask&(1<<indx['a']))==0)? tc[s[i]-'a']['a'-'a'] + rec(i+1,mask|(1<<indx['a']),indx['a'],dp):  10000000);
    x = min(x,(aeiou[last]=='e' || (mask&(1<<indx['e']))==0)? tc[s[i]-'a']['e'-'a'] + rec(i+1,mask|(1<<indx['e']),indx['e'],dp):  10000000);
    x = min(x,(aeiou[last]=='i' || (mask&(1<<indx['i']))==0)? tc[s[i]-'a']['i'-'a'] + rec(i+1,mask|(1<<indx['i']),indx['i'],dp):  10000000);
    x = min(x,(aeiou[last]=='o' || (mask&(1<<indx['o']))==0)? tc[s[i]-'a']['o'-'a'] + rec(i+1,mask|(1<<indx['o']),indx['o'],dp):  10000000);
    x = min(x,(aeiou[last]=='u' || (mask&(1<<indx['u']))==0)? tc[s[i]-'a']['u'-'a'] + rec(i+1,mask|(1<<indx['u']),indx['u'],dp):  10000000);
    return dp[i][mask][last] = x;
}

void solve(int tc)
{
    cin >> n;
    cin >> s;
    vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(32,vector<int>(6,-1)));
    cout<<rec(0,0,indx[s[0]],dp)<<endl;
}

int main()
{
    life_is_a_race
    tc['a'-'a']['e'-'a']=1; tc['a'-'a']['i'-'a']=2; tc['a'-'a']['o'-'a']=3; tc['a'-'a']['u'-'a']=4;
    tc['e'-'a']['i'-'a']=1; tc['e'-'a']['o'-'a']=2; tc['e'-'a']['u'-'a']=3; tc['e'-'a']['a'-'a']=4;
    tc['i'-'a']['o'-'a']=1; tc['i'-'a']['u'-'a']=2; tc['i'-'a']['a'-'a']=3; tc['i'-'a']['e'-'a']=4;
    tc['o'-'a']['u'-'a']=1; tc['o'-'a']['a'-'a']=2; tc['o'-'a']['e'-'a']=3; tc['o'-'a']['i'-'a']=4;
    tc['u'-'a']['a'-'a']=1; tc['u'-'a']['e'-'a']=2; tc['u'-'a']['i'-'a']=3; tc['u'-'a']['o'-'a']=4;

    indx['a']=0; indx['e']=1; indx['i']=2; indx['o']=3; indx['u']=4;
    int t=1; 
    cin>>t;
    for(int i=1;i<=t;i++) solve(i);
}

Information

Submit By
Type
Submission
Problem
P1140 Vowel arrangement
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-12 15:43:50
Judged At
2024-12-12 15:43:50
Judged By
Score
10
Total Time
≥1609ms
Peak Memory
≥186.254 MiB