Submission #1053344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053344		Dennis_Jason	Miners (IOI07_miners)	C++14	0 / 100	33 ms	18172 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;
struct dinamica{
    int ind1,ind2,ind3,val;
};
dinamica dp[3][3][NMAX];// dp[type][mine][i]->food from i will go to mine[type]
int v[NMAX];
vector<int>ind(NMAX);
int check(int ind,int t_f,int mine_f,int ind_f)
{
    map<int,int>mp;
    if(v[dp[t_f][mine_f][ind_f].ind3])
         mp[v[dp[t_f][mine_f][ind_f].ind3]]++;
    if(v[dp[t_f][mine_f][ind_f].ind2])
            mp[v[dp[t_f][mine_f][ind_f].ind2]]++;
    if(v[ind])
        mp[v[ind]]++;
    if(mp.size()==3)
        return 3;
    else if(mp.size()==2)
        return 2;
    else
        return 1;
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin>>n;
    cin>>s;
    v[0]=0;
    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;
    }
    dp[1][1][1].ind3=1;
    dp[1][1][1].val=1;
    dp[2][2][1].val=1;
    dp[2][2][1].ind3=1;
    for(int i=2;i<=n;++i)
    {
        if(dp[1][1][i-1].val+check(i,1,1,i-1)>dp[2][1][i-1].val+check(i,2,1,i-1))
        {
            dp[1][1][i].val=dp[1][1][i-1].val+check(i,1,1,i-1);
            dp[1][1][i].ind1=dp[1][1][i-1].ind2;
            dp[1][1][i].ind2=dp[1][1][i-1].ind3;
            dp[1][1][i].ind3=i;
        }
        else
        {
            dp[1][1][i].val=dp[2][1][i-1].val+check(i,2,1,i-1);
            dp[1][1][i].ind1=dp[2][1][i-1].ind2;
            dp[1][1][i].ind2=dp[2][1][i-1].ind3;
            dp[1][1][i].ind3=i;

        }

        if(dp[2][2][i-1].val+ check(i,2,2,i-1)>dp[1][2][i-1].val+check(i,1,2,i-1))
        {
            dp[2][2][i].val=dp[2][2][i-1].val+ check(i,2,2,i-1);
            dp[2][2][i].ind1=dp[2][2][i-1].ind2;
            dp[2][2][i].ind2=dp[2][2][i-1].ind3;
            dp[2][2][i].ind3=i;
        }
        else
        {
            dp[2][2][i].val=dp[1][2][i-1].val+check(i,1,2,i-1);
            dp[2][2][i].ind1=dp[1][2][i-1].ind2;
            dp[2][2][i].ind2=dp[1][2][i-1].ind3;
            dp[2][2][i].ind3=i;
        }

        if(dp[2][1][i-1].val>dp[1][1][i-1].val)
        {
            dp[2][1][i]=dp[2][1][i-1];
        }
        else
        {
            dp[2][1][i]=dp[1][1][i-1];
        }

        if(dp[1][2][i-1].val>dp[2][2][i-1].val)
        {
            dp[1][2][i]=dp[1][2][i-1];
        }
        else
        {
            dp[1][2][i]=dp[2][2][i-1];
        }
    }


//    for(int i=1;i<=n;++i)
//    {
//        cout<<i<<": "<<nl;
//        cout<<"1->1"<<"    val:"<<dp[1][1][i].val<<"  ind1:"<<dp[1][1][i].ind1<<"  ind2:"<<dp[1][1][i].ind2<<"  ind3:"<<dp[1][1][i].ind3<<nl;
//        cout<<"2->2"<<"    val:"<<dp[2][2][i].val<<"  ind1:"<<dp[2][2][i].ind1<<"  ind2:"<<dp[2][2][i].ind2<<"  ind3:"<<dp[2][2][i].ind3<<nl;
//        cout<<"1->2"<<"    val:"<<dp[1][2][i].val<<"  ind1:"<<dp[1][2][i].ind1<<"  ind2:"<<dp[1][2][i].ind2<<"  ind3:"<<dp[1][2][i].ind3<<nl;
//        cout<<"2->1"<<"    val:"<<dp[2][1][i].val<<"  ind1:"<<dp[2][1][i].ind1<<"  ind2:"<<dp[2][1][i].ind2<<"  ind3:"<<dp[2][1][i].ind3<<nl;
//
//        cout<<nl<<nl;
//
//    }
    int ans=max({dp[1][1][n].val,dp[2][2][n].val,dp[1][2][n].val,dp[2][1][n].val});
    cout<<ans;



    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: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8