QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#589014#7175. Mixed MessagesmanaAC ✓8ms22592kbC++202.4kb2024-09-25 15:41:392024-09-25 15:41:39

Judging History

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

  • [2024-09-25 15:41:39]
  • 评测
  • 测评结果:AC
  • 用时:8ms
  • 内存:22592kb
  • [2024-09-25 15:41:39]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
i64 n;
string t = "spbsu";
string s;
i64 dp1[100005][6];
i64 last1[100005][6];
i64 dp2[100005][6];
i64 last2[100005][6];
void solve(){
    cin >> n;
    s.clear();
    cin >> s;

    for(int i = 0; i <= n + 1; i++){
    	for(int j = 0; j <= 5; j++){
    		dp1[i][j] = -1;
    		dp2[i][j] = -1;
    		last1[i][j] = -1;
    		last2[i][j] = -1;
    	}
    }
    for (int i = 0; i < n; i++){
    	for(int j = 0; j < 5; j++){
    		if(i > 0){
    			dp1[i][j] = dp1[i-1][j];
    			last1[i][j] = last1[i-1][j];
    		}
        }
        for(int j = 4; j >= 0; j--){
        	if(s[i] != t[j]){
        		continue;
        	}
        	if(j == 0){
        		if(dp1[i][j] == -1){
        			dp1[i][j] = 0;
        			last1[i][j] = i;
        		}
        		else{
        			dp1[i][j] = 0;
        			last1[i][j] = i;
        		}
        	}
        	else{
        		if(dp1[i][j-1] != -1){
        			dp1[i][j] = dp1[i][j-1] + (i - 1 - last1[i][j-1])*(j);
        			last1[i][j] = i;
        		}
        	}
        }
    }
    for(int i = n-1; i >= 0; i--){
    	for(int j = 0; j < 5; j++){
    		if(i < n-1){
    			dp2[i][j] = dp2[i+1][j];
    			last2[i][j] = last2[i+1][j];
    		}
        }
        for(int j = 0; j < 5; j++){
        	if(s[i] != t[j]){
        		continue;
        	}
        	if(j == 4){
        		if(dp2[i][j] == -1){
        			dp2[i][j] = 0;
        			last2[i][j] = i;
        		}
        		else{
        			dp2[i][j] = 0;
        			last2[i][j] = i;
        		}
        	}
        	else{
        		if(dp2[i][j+1] != -1){
        			dp2[i][j] = dp2[i][j+1] + (last2[i][j+1] - i - 1)*(4-j);
        			last2[i][j] = i;
        		}
        	}
        }
    }
    i64 res = 2e9;
    for (int i = 0; i < n; i++){
        for(int j = 0; j < 5; j++){
        	if(s[i] != t[j]){
        		continue;
        	}
        	if(dp1[i][j] != -1 && dp2[i][j] != -1){
        		res = min(res, dp1[i][j] + dp2[i][j]);
        	}
        	//cout << dp1[i][j] << ' ' << dp2[i][j] << ' ' << s[i] << ' ' << t[j] << ' ' << i << endl;
        }
    }
    
    cout << res << endl;
    
    return;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

	long long tt = 1;
	//cin >> tt;
	while(tt--){
		solve();
	}

    return 0;
}


詳細信息

Test #1:

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

input:

6
spbssu

output:

1

result:

ok answer is '1'

Test #2:

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

input:

15
spongebaseurban

output:

11

result:

ok answer is '11'

Test #3:

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

input:

5
spbsu

output:

0

result:

ok answer is '0'

Test #4:

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

input:

6
sppbsu

output:

1

result:

ok answer is '1'

Test #5:

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

input:

13
spbpbsaaaaaau

output:

8

result:

ok answer is '8'

Test #6:

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

input:

100
supsuuuupusbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsupbubusbsbsppbuspuspbbusppuppubuubbusbups

output:

4

result:

ok answer is '4'

Test #7:

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

input:

100
nmpnzouzoosynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhppnkjxtqsbsvxsuypgbvatxbzmkpcpnizdsmhdzkt

output:

61

result:

ok answer is '61'

Test #8:

score: 0
Accepted
time: 3ms
memory: 22468kb

input:

100000
supsuuuupupbsubsssbpbuubsppppspsusupbuusbuspupuubuspppusubsuububusbsssppbsspuspbbusppuppubuubbusbupspbsusbsuusussssbusubuupppspppusupbspbsbspubbpsuppusbbubuuubpbbubuubbuspbubpbpsbbusubussbsbubbussspbspbubbupsssuusbbssuspbssupusbpppusssppbpsspbppupsssuupbpupussupbsbuubupppubsspsubuubsbubbppuus...

output:

0

result:

ok answer is '0'

Test #9:

score: 0
Accepted
time: 4ms
memory: 22472kb

input:

100000
nmpnzouzoozynvhsqljejmgwwgmmuaptmazvneojjgapiizxdengrritcqhpcnkjxtqsjtvxsbypgbvatxbzmkpcpnizdsmhdzktphjryltupnkahdlbudksxcukgdkexxdxrtypwqttcpjspnucumswliqciutgdaztpvhbutoscnvscylauhrhchwwstonaghwlmnnrdvdbrxafacihdhstibpqyaeckfqcmeetynurqoyaxakcuoyqwuiztkzxeyqcrjqnixfucpkzljhkquwvijhnzyfxiixn...

output:

5

result:

ok answer is '5'

Test #10:

score: 0
Accepted
time: 4ms
memory: 22468kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

0

result:

ok answer is '0'

Test #11:

score: 0
Accepted
time: 3ms
memory: 22532kb

input:

100000
spppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppppp...

output:

99995

result:

ok answer is '99995'

Test #12:

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

input:

100000
spbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb...

output:

199990

result:

ok answer is '199990'

Test #13:

score: 0
Accepted
time: 7ms
memory: 22540kb

input:

100000
spbssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

99995

result:

ok answer is '99995'

Test #14:

score: 0
Accepted
time: 3ms
memory: 22472kb

input:

100000
spbsuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu...

output:

0

result:

ok answer is '0'

Test #15:

score: 0
Accepted
time: 7ms
memory: 22580kb

input:

100000
sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss...

output:

79996

result:

ok answer is '79996'

Test #16:

score: 0
Accepted
time: 3ms
memory: 22468kb

input:

100000
spspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspspsps...

output:

6

result:

ok answer is '6'

Test #17:

score: 0
Accepted
time: 4ms
memory: 22592kb

input:

100000
spbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspbsuspb...

output:

0

result:

ok answer is '0'

Test #18:

score: 0
Accepted
time: 8ms
memory: 22468kb

input:

100000
spbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbspbsp...

output:

2

result:

ok answer is '2'

Test #19:

score: 0
Accepted
time: 6ms
memory: 22468kb

input:

100000
aausuabubupppauppuaupapaapaaaspbusssbapuuupapbusbpsauppsuppbapuassububbsssupappsbaauauauausubusppsbbsppsasupbusaauaaasbasuubusaaupupbuapsasaabsspaaasabbbpaappsuspbpappapssbsupupbusuuabbsuupusupsbabbbaauspauuasbspbubauupsuusspusupppbbbbuupbusssussupbbssaauubuusbsubabubssuapuspbabpauuaaaaaaasbs...

output:

0

result:

ok answer is '0'

Test #20:

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

input:

100000
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

0

result:

ok answer is '0'

Extra Test:

score: 0
Extra Test Passed