Submission #819824

#	Time	Username	Problem	Language	Result	Execution time	Memory
819824		canadavid1	Miners (IOI07_miners)	C++17	0 / 100	183 ms	111540 KiB

miners

#include <bits/stdc++.h>
using namespace std;

using i8 = int8_t;

vector<array<int,256>> dp;

int produce(i8 a,i8 b,i8 c)
{
    bool s[4]{};
    s[a] = true;
    s[b] = true;
    s[c] = true;
    return ((int)s[1]) + ((int)s[2]) + ((int)s[3]);
}
int toidx(pair<i8,i8> h1,pair<i8,i8> h2)
{
    //if(!h1.first || !h1.second || !h2.first || !h2.second) return 0;
    return 4*4*4*h1.first + 4*4*h1.second + 4*h2.first + h2.second;
}
int toid(char s)
{
    switch(s)
    {
        case 'B': return 1;
        case 'M': return 2;
        case 'F': return 3;
        default: __builtin_unreachable();
    }
}
int ct = 0;
int mct = 0;
int best(int off,string& s,pair<i8,i8> h1={0,0}, pair<i8,i8> h2={0,0})
{
    if(off >= s.size()) return 0;
    ct++;
    if (dp[off][toidx(h1,h2)]) return dp[off][toidx(h1,h2)];
    mct++;
    int max_produce = -1;
    // h1
    pair<i8,i8> h1p = {h1.second,toid(s[off])};
    max_produce = max(max_produce,produce(h1.first,h1.second,toid(s[off]))+best(off+1,s,h1p,h2));
    pair<i8,i8> h2p = {h2.second,toid(s[off])};
    max_produce = max(max_produce,produce(h2.first,h2.second,toid(s[off]))+best(off+1,s,h1,h2p));

    if(h1.second && h2.second) dp[off][toidx(h1,h2)] = max_produce;
    return max_produce;
}

int main()
{
    int N;
    cin >> N;
    string s(N,'\0');
    dp.assign(N,array<int,256>{});
    for(auto &&i : s) cin >> i;
    cout << best(0,s) << "\n";
    cout << ct << " " << mct << "\n";
}

Compilation message (stderr)

miners.cpp: In function 'int best(int, std::string&, std::pair<signed char, signed char>, std::pair<signed char, signed char>)':
miners.cpp:35:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if(off >= s.size()) return 0;
      |        ~~~~^~~~~~~~~~~

• 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