# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
442776 |
2021-07-09T03:39:02 Z |
cpp219 |
Miners (IOI07_miners) |
C++14 |
|
214 ms |
113516 KB |
#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;
char c;
ll a[N],n,dp[N][4][4][4][4];
ll f(ll pos,ll have11,ll have12,ll have21,ll have22){
ll &val = dp[pos][have11][have12][have21][have22];
if (pos > n) return 0;
if (val != -1) return val;
ll ans = 0,now = a[pos],inc1 = 1,inc2 = 1;
if (now != have11 && have11) inc1++;
if (now != have12 && have11 != have12 && have12) inc1++;
if (now != have21 && have21) inc2++;
if (now != have22 && have21 != have22 && have22) inc2++;
ans = max(inc1 + f(pos + 1,now,have11,have21,have22),inc2 + f(pos + 1,have11,have12,now,have21));
return val = ans;
}
int main(){
ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
#define task "tst"
if (fopen(task".INP","r")){
freopen(task".INP","r",stdin);
//freopen(task".OUT","w",stdout);
}
cin>>n;
for (ll i = 1;i <= n;i++){
cin>>c;
if (c == 'F') a[i] = 1;
else if (c == 'M') a[i] = 2;
else a[i] = 3;
}
memset(dp,-1,sizeof(dp));
cout<<f(1,0,0,0,0);
}
Compilation message
miners.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
1 | #pragma GCC optimization O2
|
miners.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
2 | #pragma GCC optimization "unroll-loop"
|
miners.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
3 | #pragma target ("avx2")
|
miners.cpp: In function 'int main()':
miners.cpp:38:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
38 | freopen(task".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
100488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
100404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
100420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
100428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
100416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
54 ms |
100456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
53 ms |
100500 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
101164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
101776 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
94 ms |
103724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
150 ms |
110256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
214 ms |
113516 KB |
Output is correct |