oj.uz

Submission #819834

# Submission time Handle Problem Language Result Execution time Memory
819834 2023-08-10T14:04:10 Z canadavid1 Miners (IOI07_miners) C++17
100 / 100
 180 ms 111636 KB 
#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";
  #ifndef EVAL
    cout << ct << " " << mct << "\n";
  #endif
}

Compilation message

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
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5812 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 11444 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 28068 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 83800 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 111636 KB Output is correct