oj.uz

Submission #330649

# Submission time Handle Problem Language Result Execution time Memory
330649 2020-11-26T04:28:23 Z sin22766 Miners (IOI07_miners) C++11
100 / 100
 491 ms 876 KB 
#include <bits/stdc++.h>

using namespace std;

int dp[2][4][4][4][4];
int food[100005];
// Food / 1st Mine Last/ 1st Mine LastLast/ 2nd Mine Last/ 2nd Mine LastLast/

int check_ore(int f, int s, int t) {
    int cnt = 0;
    for (int i = 1; i <= 3; ++i) {
        if(f == i || s == i || t == i)
            cnt++;
    }
    return cnt;
}

int main() {
    int n;
    char temp[100005];
    scanf("%d%s", &n, temp + 1);

    for (int i = 1; i <= n; ++i) {
        food[i] = (temp[i] == 'M') ? 1 : (temp[i] == 'F') ? 2 : 3;
    }

    //None = 0, M1, F2, B3

    for (int x = n + 1; x >= 1; --x) {
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                for (int k = 0; k < 4; ++k) {
                    for (int l = 0; l < 4; ++l) {
                        if (x == n+1) {
                            dp[x % 2][i][j][k][l] = 0;
                        } else {
                            dp[x % 2][i][j][k][l] = max(check_ore(food[x], i, j) + dp[(x % 2) ^ 1][food[x]][i][k][l],
                                                        check_ore(food[x], k, l) + dp[(x % 2) ^ 1][i][j][food[x]][k]);
                        }
                    }
                }
            }
        }
    }

    cout << dp[1][0][0][0][0];
    return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   21 |     scanf("%d%s", &n, temp + 1);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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