제출 #351175

#제출 시각아이디문제언어결과실행 시간메모리
351175apostoldaniel854Miners (IOI07_miners)C++14
0 / 100
1217 ms644 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define pb push_back #define dbg(x) cerr << #x << " " << x << "\n" inline int code (char ch) { if (ch == 'M') return 1; if (ch == 'F') return 2; return 3; } const int MAX_MASK = (1 << 6); int f[4]; inline int get_dist (int mask) { f[1] = f[2] = f[3]; while (mask) { f[mask & 3] = 1; mask /= 4; } return f[1] + f[2] + f[3]; } inline int add (int &mask, int &x) { return ((mask << 2) + x) & (MAX_MASK - 1); } inline void upd (int &a, int b) { if (a < b) a = b; } int dp[1 + MAX_MASK][1 + MAX_MASK]; int new_dp[1 + MAX_MASK][1 + MAX_MASK]; int main () { ios::sync_with_stdio (false); cin.tie (); cout.tie (0); register int n; cin >> n; string shipments_order; cin >> shipments_order; for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++) for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) dp[first_mine][second_mine] = -1; dp[0][0] = 0; for (char shipment : shipments_order) { register int x = code (shipment); for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++) for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) new_dp[first_mine][second_mine] = -1; for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++) for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) { register int value = dp[first_mine][second_mine]; if (value >= 0) { register int new_first_mine = add (first_mine, x); register int new_second_mine = add (second_mine, x); upd (new_dp[new_first_mine][second_mine], value + get_dist (new_first_mine)); upd (new_dp[first_mine][new_second_mine], value + get_dist (new_second_mine)); } } for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++) for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) dp[first_mine][second_mine] = new_dp[first_mine][second_mine]; } register int ans = 0; for (register int first_mine = 0; first_mine < MAX_MASK; first_mine++) for (register int second_mine = 0; second_mine < MAX_MASK; second_mine++) upd (ans, dp[first_mine][second_mine]); cout << ans << "\n"; return 0; }
#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...