QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236249#7175. Mixed MessagesUFRJ#AC ✓2ms4272kbC++20774b2023-11-03 19:16:332023-11-03 19:16:33

Judging History

This is the latest submission verdict.

  • [2023-11-03 19:16:33]
  • Judged
  • Verdict: AC
  • Time: 2ms
  • Memory: 4272kb
  • [2023-11-03 19:16:33]
  • Submitted

answer

#include "bits/stdc++.h"

using namespace std;
using lint = int64_t;
const int inf = 1e9;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    string s;
    cin>>n>>s;
    vector<int>dp(n, inf);
    string t = "spbsu";
    for(int i=0;i<n;i++) if(s[i] == t[0]) dp[i] = -i;
    for(int j=1;j<5;j++){
        int mn = inf;
        vector<int>ndp(n, inf);
        for(int i=0;i<n;i++){
            mn = min(mn, dp[i]);
            if(s[i] == t[j]){
                int cnt = 0;
                if(j == 1) cnt = -i;
                if(j == 3 || j == 4) cnt = i;
                ndp[i] = mn + cnt;
            }
        }
        swap(dp, ndp);
    }
    cout<< *min_element(dp.begin(), dp.end()) - 6<<"\n";  

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3588kb

input:

6
spbssu

output:

1

result:

ok answer is '1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

15
spongebaseurban

output:

11

result:

ok answer is '11'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

5
spbsu

output:

0

result:

ok answer is '0'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

6
sppbsu

output:

1

result:

ok answer is '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3484kb

input:

13
spbpbsaaaaaau

output:

8

result:

ok answer is '8'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3528kb

input:

100
supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups

output:

4

result:

ok answer is '4'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3548kb

input:

100
nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt

output:

61

result:

ok answer is '61'

Test #8:

score: 0
Accepted
time: 2ms
memory: 4132kb

input:

100000
supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 0ms
memory: 4272kb

input:

100000
nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...

output:

5

result:

ok answer is '5'

Test #10:

score: 0
Accepted
time: 1ms
memory: 4132kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 1ms
memory: 4156kb

input:

100000
spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

99995

result:

ok answer is '99995'

Test #12:

score: 0
Accepted
time: 1ms
memory: 4140kb

input:

100000
spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

199990

result:

ok answer is '199990'

Test #13:

score: 0
Accepted
time: 0ms
memory: 4132kb

input:

100000
spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

99995

result:

ok answer is '99995'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4140kb

input:

100000
spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

0

result:

ok answer is '0'

Test #15:

score: 0
Accepted
time: 0ms
memory: 4228kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

79996

result:

ok answer is '79996'

Test #16:

score: 0
Accepted
time: 1ms
memory: 4160kb

input:

100000
spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...

output:

6

result:

ok answer is '6'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4068kb

input:

100000
spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...

output:

0

result:

ok answer is '0'

Test #18:

score: 0
Accepted
time: 1ms
memory: 4096kb

input:

100000
spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 0ms
memory: 4152kb

input:

100000
aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...

output:

0

result:

ok answer is '0'

Test #20:

score: 0
Accepted
time: 1ms
memory: 4152kb

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Extra Test:

score: 0
Extra Test Passed