Submission #989882

#	Time	Username	Problem	Language	Result	Execution time	Memory
989882		PedroBigMan	Miners (IOI07_miners)	C++14	100 / 100	355 ms	620 KiB

miners

#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro "<<i<<endl
#define INF 100000000
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007;

template<class A=ll> 
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

vector<string> states; ll S; string s;
vector<vector<ll> > curstate, newstate;
unordered_map<string,ll> m;

ll num_dif(string str)
{
    set<char> dif;
    REP(i,0,str.size()) {dif.insert(str[i]);}
    return dif.size();
}

void update(ll a,ll b,ll c, char added)
{
    if(c==1) {swap(a,b);}
    ll extra = num_dif(states[a]+added);
    string newa = states[a]+added; if(newa.size()==3) {newa.erase(newa.begin());}
    ll upd_a = m[newa]; ll upd_b = b;
    if(c==1) {swap(upd_a,upd_b);}
    newstate[upd_a][upd_b]=max(newstate[upd_a][upd_b],curstate[a][b]+extra);
    newstate[upd_b][upd_a]=newstate[upd_a][upd_b];
    //cout<<"("<<states[a]<<","<<states[b]<<"),("<<states[upd_a]<<","<<states[upd_b]<<"): "<<added<<" "<<c<<" "<<extra<<endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
	cout.precision(20);
	ll N; cin>>N; cin>>s;
    states = {"","M","F","B","MM","MF","MB","FM","FF","FB","BM","BF","BB"}; S = states.size();
    REP(i,0,S) {m[states[i]]=i;}
    curstate = vector<vector<ll> >(S,vector<ll>(S,-INF)); newstate = vector<vector<ll> >(S,vector<ll>(S,-INF));
    curstate[0][0]=0;
    REP(i,0,N)
    {
        REP(a,0,S) {REP(b,0,S) {newstate[a][b]=-INF;}}
        REP(a,0,S)
        {
            REP(b,0,a+1)
            {
                if(curstate[a][b]<0) {continue;}
                REP(c,0,2)
                {
                    update(a,b,c,s[i]);
                }
            }
        }
        REP(a,0,S) {REP(b,0,S) {curstate[a][b]=newstate[a][b];}}
    }
    ll ans = 0;
    REP(a,0,S) {REP(b,0,a+1) {ans=max(ans,curstate[a][b]);}}
    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

miners.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization ("O3")
      | 
miners.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      |

• 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