제출 #797810

#제출 시각아이디문제언어결과실행 시간메모리
797810asdfgraceMiners (IOI07_miners)C++17
100 / 100
98 ms100764 KiB
#include <bits/stdc++.h> using namespace std; int dp[100005][4][4][4][4]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s; cin >> s; memset(dp, -1, sizeof(dp)); dp[0][3][3][3][3] = 0; for (int i = 0; i < n; ++i) { for (int a1 = 0; a1 < 4; ++a1) { for (int a2 = 0; a2 < 4; ++a2) { for (int b1 = 0; b1 < 4; ++b1) { for (int b2 = 0; b2 < 4; ++b2) { if (dp[i][a1][a2][b1][b2] < 0) continue; int cur = (s[i] == 'M' ? 0 : (s[i] == 'F' ? 1 : 2)); int amask = (((1 << cur) | (1 << a1)) | (1 << a2)); if (amask >= 8) amask -= 8; int acnt = __builtin_popcount(amask); int bmask = (((1 << cur) | (1 << b1)) | (1 << b2)); if (bmask >= 8) bmask -= 8; int bcnt = __builtin_popcount(bmask); dp[i + 1][a2][cur][b1][b2] = max(dp[i + 1][a2][cur][b1][b2], dp[i][a1][a2][b1][b2] + acnt); dp[i + 1][a1][a2][b2][cur] = max(dp[i + 1][a1][a2][b2][cur], dp[i][a1][a2][b1][b2] + bcnt); } } } } } int ans = 0; for (int a1 = 0; a1 < 4; ++a1) { for (int a2 = 0; a2 < 4; ++a2) { for (int b1 = 0; b1 < 4; ++b1) { for (int b2 = 0; b2 < 4; ++b2) { ans = max(ans, dp[n][a1][a2][b1][b2]); } } } } cout << ans << '\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...