Submission #819824

#TimeUsernameProblemLanguageResultExecution timeMemory
819824canadavid1Miners (IOI07_miners)C++17
0 / 100
183 ms111540 KiB
#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;
      |        ~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...