Submission #166122

#	Time	Username	Problem	Language	Result	Execution time	Memory
166122		MarcoMendoza1	Miners (IOI07_miners)	C++14	84 / 100	1580 ms	108544 KiB

miners

#include <iostream>
#include <unordered_map>
#include <cstring>

using namespace std;

const int MAXN = 100000;
char shipment[MAXN + 2];
int N;

int memo[MAXN][4][4][4][4];

struct Prev {
    char a[2][2];
};

Prev give(int pos, int mine, Prev prev) {
    prev.a[mine][0] = prev.a[mine][1];
    prev.a[mine][1] = shipment[pos];
    return prev;
}

int diff(int pos, int mine, Prev prev) {
    unordered_map<char, int> foodCount;
    foodCount[prev.a[mine][0]]++;
    foodCount[prev.a[mine][1]]++;
    foodCount[shipment[pos]]++;
    int typesOfFood = 0;
    if (foodCount['M'])
        typesOfFood++;
    if (foodCount['F'])
        typesOfFood++;
    if (foodCount['B'])
        typesOfFood++;
    return typesOfFood;
}

unordered_map<char, int> conversion;

int F(int pos, Prev prev) {
    if (pos == N) {
        return 0;
    } else {
        int &m = memo[pos][ conversion[prev.a[0][0]] ][ conversion[prev.a[0][1]] ][ conversion[prev.a[1][0]] ][ conversion[prev.a[1][1]] ];
        if (m==-1)
        m = max(
                   F(pos + 1, give(pos, 0, prev)) + diff(pos, 0, prev),
                   F(pos + 1, give(pos, 1, prev)) + diff(pos, 1, prev)
               );
        return m;
    }
}

int main() {
    memset(memo,-1,sizeof memo);
    conversion[0] = 0;
    conversion['M'] = 1;
    conversion['F'] = 2;
    conversion['B'] = 3;
    cin >> N >> shipment;
    cout << F(0, {{{0, 0}, {0, 0}}}) << '\n';
}

• 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: 0 / 8
• Subtask 12: 0 / 8