제출 #166122

#제출 시각아이디문제언어결과실행 시간메모리
166122MarcoMendoza1Miners (IOI07_miners)C++14
84 / 100
1580 ms108544 KiB
#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';
}
#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...