Submission #1053477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053477		Dennis_Jason	Miners (IOI07_miners)	C++14	100 / 100	554 ms	211292 KiB

miners

#include <bits/stdc++.h>
#define NMAX 100001
#define int long long
#define pb push_back
#define eb emplace_back
#define MOD 1000000007
#define nl '\n'
#define INF  1000000007
#define LLONG_MAX 9223372036854775807
#define pii pair<int,int>
#define tpl tuple<int,int,int,int>
//#pragma GCC optimize("O3")
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
/*
 *
 *
    ----------------DEMONSTRATION-------------------


        MBMFFB

        mine1       mine2
        MBF           MFB

        1+2+3=6       1+2+3=6


        MBMFFB

    ---------------------END------------------------

 */
/*-------------Initialize------------*/
int n;
string s;
int v[NMAX];
int ans;
int dp[NMAX][4][4][4][4];
int calc(int a,int b,int c)
{
    map<int,int>mp;
    if(a)
        mp[a]=1;
    if(b)
        mp[b]=1;
    if(c)
        mp[c]=1;
    if(mp.size()==3)
        return 3;
    if(mp.size()==2)
        return 2;
    return 1;
}
int solve(int ind,int a_i1,int a_i2,int b_i1,int b_i2)
{
    if(ind==n+1)
        return 0;
    int &ans=dp[ind][a_i1][a_i2][b_i1][b_i2];
    if(ans!=-1)
        return ans;
    int a=calc(a_i1,a_i2,v[ind]);
    int b=calc(b_i1,b_i2,v[ind]);

    ans=max(
            solve(ind+1,v[ind],a_i1,b_i1,b_i2)+a,
            solve(ind+1,a_i1,a_i2,v[ind],b_i1)+b
            );
    return ans;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n;
    cin>>s;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;++i) {
        if (s[i - 1] == 'M')
            v[i] = 1;
        else if (s[i - 1] == 'F')
            v[i] = 2;
        else
            v[i] = 3;
    }

    cout<<solve(1,0,0,0,0);
    return 0;
}

Compilation message (stderr)

miners.cpp:9: warning: "LLONG_MAX" redefined
    9 | #define LLONG_MAX 9223372036854775807
      | 
In file included from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:195,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/syslimits.h:7,
                 from /usr/lib/gcc/x86_64-linux-gnu/10/include/limits.h:34,
                 from /usr/include/c++/10/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:39,
                 from miners.cpp:1:
/usr/include/limits.h:135: note: this is the location of the previous definition
  135 | #  define LLONG_MAX __LONG_LONG_MAX__
      |

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8