oj.uz

Submission #703054

# Submission time Handle Problem Language Result Execution time Memory
703054 2023-02-25T19:38:31 Z LucaLucaM Miners (IOI07_miners) C++17
100 / 100
 154 ms 100740 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 308 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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