제출 #396674

#제출 시각아이디문제언어결과실행 시간메모리
396674MarcoMeijerMiners (IOI07_miners)C++14
100 / 100
625 ms628 KiB
#include <bits/stdc++.h> using namespace std; // macros typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef pair<ll, ll> lll; typedef tuple<int, int, int> iii; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<iii> viii; typedef vector<ll> vll; typedef vector<lll> vlll; #define REP(a,b,c) for(int a=int(b); a<int(c); a++) #define RE(a,c) REP(a,0,c) #define RE1(a,c) REP(a,1,c+1) #define REI(a,b,c) REP(a,b,c+1) #define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--) #define FOR(a,b) for(auto& a : b) #define all(a) a.begin(), a.end() #define INF 1e18 #define EPS 1e-9 #define pb push_back #define popb pop_back #define fi first #define se second mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // input template<class T> void IN(T& x) {cin >> x;} template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); } // output template<class T1, class T2> void OUT(const pair<T1,T2>& x); template<class T> void OUT(const vector<T>& x); template<class T> void OUT(const T& x) {cout << x;} template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); } template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);} template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);} template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); } template<class H> void OUTLS(const H& h) {OUTL(h); } template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); } // dp template<class T> bool ckmin(T&a, const T&b) { bool bl = a > b; a = min(a,b); return bl;} template<class T> bool ckmax(T&a, const T&b) { bool bl = a < b; a = max(a,b); return bl;} void program(); int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); program(); } //===================// // begin program // //===================// const int MX = 1e5+2; const int N = (1<<20); int n, m=0; string s; int f[4][4][4]; int profit[45][4]; int nextF[45][4]; int countDif(vi f) { set<int> s; FOR(i,f) s.insert(i); return s.size(); } void preCalc() { f[0][0][0] = m++; RE1(i,3) f[i][0][0] = m++; RE1(i,3) RE1(j,3) f[i][j][0] = m++; RE1(i,3) RE1(j,3) RE1(k,3) f[i][j][k] = m++; RE1(l,3) { profit[f[0][0][0]][l] = 1; RE1(i,3) profit[f[i][0][0]][l] = countDif({l,i}); RE1(i,3) RE1(j,3) profit[f[i][j][0]][l] = countDif({l,i,j}); RE1(i,3) RE1(j,3) RE1(k,3) profit[f[i][j][k]][l] = countDif({l,i,j}); } RE1(l,3) { nextF[f[0][0][0]][l] = f[l][0][0]; RE1(i,3) nextF[f[i][0][0]][l] = f[l][i][0]; RE1(i,3) RE1(j,3) nextF[f[i][j][0]][l] = f[l][i][j]; RE1(i,3) RE1(j,3) RE1(k,3) nextF[f[i][j][k]][l] = f[l][i][j]; } } int dp[2][45][45]; void program() { IN(n,s); FOR(c,s) { if(c == 'M') c = 1; if(c == 'F') c = 2; if(c == 'B') c = 3; } preCalc(); memset(dp,-1,sizeof(dp)); dp[0][0][0] = 0; int ans = 0; RE(i,n) { int c = s[i]; RE(j,m) RE(k,m) { if(dp[i%2][j][k] == -1) continue; ckmax(dp[(i+1)%2][nextF[j][c]][k], profit[j][c] + dp[i%2][j][k]); ckmax(dp[(i+1)%2][j][nextF[k][c]], profit[k][c] + dp[i%2][j][k]); ckmax(ans, profit[j][c] + dp[i%2][j][k]); ckmax(ans, profit[k][c] + dp[i%2][j][k]); } RE(j,m) RE(k,m) dp[i%2][j][k] = -1; } OUTL(ans); }
#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...