Submission #703054

#	Time	Username	Problem	Language	Result	Execution time	Memory
703054		LucaLucaM	Miners (IOI07_miners)	C++17	100 / 100	154 ms	100740 KiB

miners

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 1e5;

/**
pt fiecare raspunsul depine doar de ultimele doua pe care le am pus
=>
dp[n][x1][x2][y1][y2] = suma pe care o obtinem daca ajungem sa fie pt prima mina (x1, y1) si pt a doua mina (x2, y2)

NIMIC -> 0
MEAT -> 1
BREAD -> 2
FISH -> 3
**/

int dp[NMAX + 5][4][4][4][4];

int care (char ch)
{
    if (ch == 'M')
        return 1;
    if (ch == 'B')
        return 2;
    return 3;
}

int distincte (int a, int b, int c)
{
    bool f[4] = {};
    f[a] = f[b] = f[c] = true;
    return f[1] + f[2] + f[3];
}

int main()
{
    int n;
    cin >> n;

    string s;
    cin >> s;

    for (int i=0; i<=n; i++)
    {
        for (int x1=0; x1<4; x1++)
            for (int y1=0; y1<4; y1++)
                for (int x2=0; x2<4; x2++)
                    for (int y2=0; y2<4; y2++)
                        dp[i][x1][y1][x2][y2] = -1e9;
    }

    dp[0][0][0][0][0] = 0; // daca nu punem nimic

    for (int i=1; i<=n; i++) // unde punem al i-lea
    {
        int c = care(s[i-1]);

        for (int x1=0; x1<4; x1++)
        {
            for (int x2=0; x2<4; x2++)
            {
                for (int y1=0; y1<4; y1++)
                {
                    for (int y2=0; y2<4; y2++)
                    {
                        int add;

                        /// punem in prima
                        add = distincte(x1, x2, c);
                        dp[i][x2][c][y1][y2] = max(dp[i][x2][c][y1][y2], dp[i-1][x1][x2][y1][y2] + add);

                        /// punem in a doua
                        add = distincte(y1, y2, c);
                        dp[i][x1][x2][y2][c] = max(dp[i][x1][x2][y2][c], dp[i-1][x1][x2][y1][y2] + add);
                    }
                }
            }
        }
    }

    int ans = -1e9;

    for (int x1=0; x1<4; x1++)
    {
        for (int y1=0; y1<4; y1++)
        {
            for (int x2=0; x2<4; x2++)
            {
                for (int y2=0; y2<4; y2++)
                    ans = max(ans, dp[n][x1][x2][y1][y2]);
            }
        }
    }

    cout << ans;

    return 0;
}

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