# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
70384 |
2018-08-22T18:29:30 Z |
doowey |
Miners (IOI07_miners) |
C++14 |
|
210 ms |
100968 KB |
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
#define fi first
#define se second
#define mp make_pair
#define fastIO std::ios::sync_with_stdio(false);cin.tie(NULL);
#define TEST freopen("in.txt","r",stdin);
#define ones(a) __builtin_popcount(a);
#define pq priority_queue
const int N = (int)1e5 + 9;
int dp[N][4][4][4][4];
int k;
int calc(int a, int b, int c){
k = 0;
if(a != 0)
k ++ ;
if(b != 0)
k ++ ;
if(c != 0)
k ++ ;
if(k == 1)
return 1;
if(k == 2)
return (a != b) + 1;
if(a == b and b == c)
return 1;
else if(a == b or b == c or a == c)
return 2;
else
return 3;
}
void upd(int &a, int b){
a = max(a, b);
}
int main(){
fastIO;
memset(dp, -10000000, sizeof dp);
dp[0][0][0][0][0] = 0;
int n;
cin >> n;
char k;
int y;
int ans = 0;
for(int i = 1; i <= n;i ++ ){
cin >> k;
if(k == 'M')
y = 1;
else if(k == 'F')
y = 2;
else
y = 3;
// send this to mine 1:
for(int t1 = 0; t1 < 4; t1 ++ ){
for(int t2 = 0; t2 < 4; t2 ++ ){
for(int s1 = 0; s1 < 4; s1 ++ ){
for(int s2 = 0; s2 < 4; s2 ++ ){
upd(dp[i][y][t1][s1][s2], dp[i - 1][t1][t2][s1][s2] + calc(y, t1, t2));
upd(ans, dp[i][y][t1][s1][s2]);
if(s1 == 0)
continue;
}
}
}
if(t1 == 0)
continue;
}
// send this to mine 2:
for(int t1 = 0; t1 < 4; t1 ++ ){
for(int t2 = 0; t2 < 4; t2 ++ ){
for(int s1 = 0; s1 < 4; s1 ++ ){
for(int s2 = 0; s2 < 4; s2 ++ ){
upd(dp[i][t1][t2][y][s1], dp[i - 1][t1][t2][s1][s2] + calc(y, s1, s2));
upd(ans, dp[i][t1][t2][y][s1]);
if(s1 == 0)
continue;
}
}
}
if(t1 == 0)
continue;
}
}
cout << ans << " ";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
100600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
100600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
91 ms |
100668 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
100748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
100748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
100756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
90 ms |
100780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
96 ms |
100780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
86 ms |
100780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
102 ms |
100836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
173 ms |
100860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
100968 KB |
Output is correct |