# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
536307 |
2022-03-12T19:07:58 Z |
kebine |
Miners (IOI07_miners) |
C++17 |
|
268 ms |
201784 KB |
#include <bits/stdc++.h>
using namespace std;
#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >
int main() {
nyahalo
string s;
long long n, x, cnt, ans = -1e12;
cin >> n >> s;
long long a[n+1];
for (long long i=1; i<=n; i++) {
if (s[i-1] == 'M') {
a[i] = 1;
} else if (s[i-1] == 'F') {
a[i] = 2;
} else {
a[i] = 3;
}
}
long long dp[n+1][4][4][4][4];
for (long long i=0; i<4; i++) {
for (long long j=0; j<4; j++) {
for (long long ii=0; ii<4; ii++) {
for (long long jj=0; jj<4; jj++) {
dp[0][i][j][ii][jj] = -1e9;
}
}
}
}
dp[0][0][0][0][0] = 0;
for (long long i=1; i<=n; i++) {
for (long long ii=0; ii<4; ii++) {
for (long long jj=0; jj<4; jj++) {
for (long long iii=0; iii<4; iii++) {
for (long long jjj=0; jjj<4; jjj++) {
dp[i][ii][jj][iii][jjj] = dp[i-1][ii][jj][iii][jjj];
}
}
}
}
x = a[i];
for (long long ii=0; ii<4; ii++) {
for (long long jj=0; jj<4; jj++) {
for (long long iii=0; iii<4; iii++) {
for (long long jjj=0; jjj<4; jjj++) {
if (dp[i-1][ii][jj][iii][jjj] == -1e9) {
continue;
}
if (ii == 0) {
if (jj == x || jj == 0) {
dp[i][jj][x][iii][jjj] = max(dp[i][jj][x][iii][jjj], dp[i-1][ii][jj][iii][jjj]+1);
} else {
dp[i][jj][x][iii][jjj] = max(dp[i][jj][x][iii][jjj], dp[i-1][ii][jj][iii][jjj]+2);
}
} else {
cnt = 1;
if (jj != ii) {
cnt++;
}
if (cnt == 2) {
if (x != jj && x != ii) {
cnt++;
}
} else {
if (x != jj || x != ii) {
cnt++;
}
}
dp[i][jj][x][iii][jjj] = max(dp[i][jj][x][iii][jjj], dp[i-1][ii][jj][iii][jjj]+cnt);
}
if (iii == 0) {
if (jjj == x || jjj == 0) {
dp[i][ii][jj][jjj][x] = max(dp[i][ii][jj][jjj][x], dp[i-1][ii][jj][iii][jjj]+1);
} else {
dp[i][ii][jj][jjj][x] = max(dp[i][ii][jj][jjj][x], dp[i-1][ii][jj][iii][jjj]+2);
}
} else {
cnt = 1;
if (jjj != iii) {
cnt++;
}
if (cnt == 2) {
if (x != jjj && x != iii) {
cnt++;
}
} else {
if (x != jjj || x != iii) {
cnt++;
}
}
dp[i][ii][jj][jjj][x] = max(dp[i][ii][jj][jjj][x], dp[i-1][ii][jj][iii][jjj]+cnt);
}
}
}
}
}
}
for (long long ii=0; ii<4; ii++) {
for (long long jj=0; jj<4; jj++) {
for (long long iii=0; iii<4; iii++) {
for (long long jjj=0; jjj<4; jjj++) {
ans = max(ans, dp[n][ii][jj][iii][jjj]);
}
}
}
}
cout << ans << "\n";
otsumiko
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
2260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
10324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
31 ms |
20424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
76 ms |
50672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
207 ms |
151440 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
268 ms |
201784 KB |
Output is correct |