oj.uz

Submission #305503

# Submission time Handle Problem Language Result Execution time Memory
305503 2020-09-23T11:23:33 Z Akashi Miners (IOI07_miners) C++14
100 / 100
 328 ms 508 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int DIM = 1e5 + 5;

int n;
int dp[2][4][4][4][4];
char s[DIM];

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

void calc(int &dp, int &aux, int a, int b, int c) {
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);

    if (a == b) a = 0;
    if (b == c) b = 0;

    int ad = (a != 0) + (b != 0) + (c != 0);

    dp = max(dp, aux + ad);
}

int main() {
    #ifdef HOME
    freopen("miners.in", "r", stdin);
    freopen("miners.out", "w", stdout);
    #endif // HOME

    scanf("%d", &n);
    scanf("%s", s);

    memset(dp, -0x3f, sizeof(dp));

    dp[0][0][0][0][0] = 0;

    for (int i = 1, l = 1; i <= n ; ++i, l = 1 - l) {
        int tip = trans(s[i - 1]);

        for (int a = 0; a <= 3 ; ++a) for(int b = 0; b <= 3 ; ++b) for (int x = 0; x <= 3 ; ++x) for (int y = 0; y <= 3 ; ++y)
            dp[l][a][b][x][y] = -INF;

        for (int a = 0; a <= 3 ; ++a) for(int b = 0; b <= 3 ; ++b) for (int x = 0; x <= 3 ; ++x) for (int y = 0; y <= 3 ; ++y) {
            calc(dp[l][b][tip][x][y], dp[1 - l][a][b][x][y], a, b, tip);
            calc(dp[l][a][b][y][tip], dp[1 - l][a][b][x][y], x, y, tip);
        }
    }

    int ans = 0;
    for (int a = 0; a <= 3 ; ++a) for(int b = 0; b <= 3 ; ++b) for (int x = 0; x <= 3 ; ++x) for (int y = 0; y <= 3 ; ++y)
        ans = max(ans, dp[n % 2][a][b][x][y]);

    printf("%d", ans);
    return 0;
}

Compilation message

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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