# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
54558 |
2018-07-04T05:29:44 Z |
윤교준(#1492) |
Miners (IOI07_miners) |
C++11 |
|
83 ms |
976 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int BC[] = { 0, 1, 1, 2, 1, 2, 2, 3 };
const int MAXN = 100005;
int dp[2][16][16];
int A[MAXN];
int N, Ans;
pii f(int key, int c) {
int a[3] = { (key&12)>>2, key&3, c };
int t = 0;
for(int i = 0; i < 3; i++)
t |= (1<<a[i]);
t >>= 1;
return pii((a[1]<<2) + a[2], BC[t]);
}
int main() {
//freopen("input.txt", "r", stdin);
scanf("%d", &N);
for(int i = 1; i <= N; i++) {
char c; scanf(" %c", &c);
if('B' == c) A[i] = 1;
else if('M' == c) A[i] = 2;
else A[i] = 3;
}
for(int i = 0; i < 2; i++) for(int j = 0; j < 16; j++)
fill(dp[i][j], dp[i][j]+16, -1);
dp[0][0][0] = 0;
for(int i = 1; i <= N; i++) {
for(int j = 0; j < 16; j++) for(int k = 0; k < 16; k++) {
int ret = dp[!(i&1)][j][k];
if(ret < 0) continue;
{
pii p = f(j, A[i]);
upmax(dp[i&1][p.first][k], ret + p.second);
}
{
pii p = f(k, A[i]);
upmax(dp[i&1][j][p.first], ret + p.second);
}
}
for(int j = 0; j < 16; j++) for(int k = 0; k < 16; k++)
dp[!(i&1)][j][k] = -1;
}
for(int i = 0; i < 16; i++) for(int j = 0; j < 16; j++)
upmax(Ans, dp[N&1][i][j]);
cout << Ans << endl;
return 0;
}
Compilation message
miners.cpp: In function 'int main()':
miners.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
miners.cpp:39:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
char c; scanf(" %c", &c);
~~~~~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
83 ms |
976 KB |
Output is correct |