제출 #1068598

#제출 시각아이디문제언어결과실행 시간메모리
1068598Halym2007Miners (IOI07_miners)C++17
100 / 100
709 ms604 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define sz size() #define ff first #define ss second #define pb push_back #define pii pair <char, int> const int N = 2e4 + 5; int dp[4][4][4][4], n, new_dp[4][4][4][4]; int jog = 0; string s; int jogap (int x, int y, int z) { int ret = 0; vector <int> v(4, 0); v[x] = 1;v[y] = 1;v[z] = 1; ret = v[1] + v[2] + v[3]; return ret; } void solve (int idx) { if (idx == n + 1) return; for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { for (int l = 0; l < 4; ++l) { for (int r = 0; r < 4; ++r) { new_dp[i][j][l][r] = -1e9; } } } } int val = 0; if (s[idx] == 'F') val = 1; else if (s[idx] == 'M') val = 2; else val = 3; for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { for (int l = 0; l < 4; ++l) { for (int r = 0; r < 4; ++r) { new_dp[j][val][l][r] = max (new_dp[j][val][l][r], dp[i][j][l][r] + jogap (i, j, val)); new_dp[i][j][r][val] = max (new_dp[i][j][r][val], dp[i][j][l][r] + jogap (l, r, val)); } } } } for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { for (int l = 0; l < 4; ++l) { for (int r = 0; r < 4; ++r) { dp[i][j][l][r] = new_dp[i][j][l][r]; } } } } solve (idx + 1); } int main () { // freopen ("input.txt", "r", stdin); ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> s; s = " " + s; for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { for (int l = 0; l < 4; ++l) { for (int r = 0; r < 4; ++r) { dp[i][j][l][r] = -1e9; } } } } dp[0][0][0][0] = 0; solve(1); for (int i = 0; i < 4; ++i) { for (int j = 0; j < 4; ++j) { for (int l = 0; l < 4; ++l) { for (int r = 0; r < 4; ++r) { jog = max (dp[i][j][l][r], jog); } } } } cout << jog; }
#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...