This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
int code (char ch) {
if (ch == 'M')
return 0;
if (ch == 'F')
return 1;
return 2;
}
inline int get_dist (vector <int> &v) {
vector <int> f (3);
for (int x : v)
f[x] = 1;
return f[0] + f[1] + f[2];
}
vector <int> add (vector <int> v, int x) {
if (v.size () < 3) {
v.pb (x);
return v;
}
else {
return {v[1], v[2], x};
}
}
void upd (int &a, int b) {
if (a < b)
a = b;
}
int main () {
ios::sync_with_stdio (false);
cin.tie (); cout.tie (0);
map <pair <vector <int>, vector <int>>, int> dp;
int n;
cin >> n;
string shipments_order;
cin >> shipments_order;
dp[{{}, {}}] = 0;
for (char shipment : shipments_order) {
int x = code (shipment);
map <pair <vector <int>, vector <int>>, int> new_dp;
for (auto prev_state : dp) {
int value = prev_state.second;
vector <int> first_mine = prev_state.first.first;
vector <int> second_mine = prev_state.first.second;
vector <int> new_first_mine = add (first_mine, x);
vector <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));
}
dp = new_dp;
}
int ans = 0;
for (auto state : dp)
ans = max (ans, state.second);
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |