제출 #404192

#제출 시각아이디문제언어결과실행 시간메모리
404192PietraMiners (IOI07_miners)C++14
100 / 100
1128 ms145604 KiB
#include<bits/stdc++.h> using namespace std ; const int maxn = 1e5 + 5 ; int n, dp[maxn][4][4][4][4], v[maxn] ; string s ; int solve(int i, int t11, int t12, int t21, int t22){ // os ultimos 2 importam qd add o novo if(i >= n) return 0 ; if(dp[i][t11][t12][t21][t22] != -1) return dp[i][t11][t12][t21][t22] ; set<int> ans1, ans2 ; if(t11 != 0) ans1.insert(t11) ; if(t12 != 0) ans1.insert(t12) ; //qto ganha ao add na mina 1 ou na 2 (qts diferentes tiver) ans1.insert(v[i]) ; ans2.insert(v[i]) ; if(t21 != 0) ans2.insert(t21) ; if(t22 != 0) ans2.insert(t22) ; return dp[i][t11][t12][t21][t22] = max(ans1.size() + solve(i+1, v[i], t11, t21, t22), ans2.size() + solve(i+1, t11, t12, v[i], t21)) ; //mlr colocar o atual em 1 ou 2? } int main(){ cin >> n ; cin >> s ; memset(dp, -1, sizeof dp) ; for(int i = 0 ; i < n ; i++){ if(s[i] == 'M') v[i] = 1 ; else if(s[i] == 'B') v[i] = 2 ; else v[i] = 3 ; } cout << solve(0, 0, 0, 0, 0) << "\n" ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...