| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 477143 | jeroenodb | Miners (IOI07_miners) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
const string types = "MFB";
int id(char c) {return types.find(c);}
constexpr int S=3*3;
int cmax(int& a, int b){return a=max(a,b);}
int main() {
int n; cin >> n;
int dp[2][S][S+1],score[S][3] = {};
for(int i=0;i<S;++i) {
int b = i%3, c = i/3;
for(int j=0;j<3;++j) {
score[i][j]+=set{b,c,j}.size();
}
}
for(int i=0;i<S;++i) fill(dp[0][i],dp[0][i]+S+1,-oo);
string s; cin >> s;
dp[0][4*id(s[0])][S]=1;
for(int k=1;k<n;++k) {
auto cur = dp[k%2], old = dp[(k-1)%2];
for(int i=0;i<S;++i) fill(cur[i],cur[i]+S+1,-oo);
int myid = id(s[k]);
for(int i=0;i<S;++i) for(int j=0;j<=S;++j) if(old[i][j]!=-oo){
cmax(cur[i/3+3*myid][j],old[i][j]+score[i][myid]);
if(j==S) {
cmax(cur[i][4*myid],old[i][j]+1);
} else {
cmax(cur[i][j/3+3*myid],old[i][j]+score[j][myid]);
}
}
// for(int i=0;i<S;++i) {
// for(int j=0;j<S;++j) {
// if(cur[i][j]!=-oo) {
// cout << setw(3) << cur[i][j];
// } else cout << " *";
// }cout << '\n';
// }
// cout << "----\n";
}
auto cur = dp[(n-1)%2];
int ans = -oo;
for(int i=0;i<S;++i) ans = max(ans,*max_element(cur[i],cur[i]+S));
cout << ans << '\n';
}