oj.uz

Submission #52167

# Submission time Handle Problem Language Result Execution time Memory
52167 2018-06-24T12:25:22 Z win11905 Miners (IOI07_miners) C++11
100 / 100
 238 ms 704 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+5, INF = 1e9;

int n, Ans, dp[2][256];
char A[N];

int get(char c) { return c == 'M' ? 1 : (c == 'F' ? 2 : 3); }

int getCost(int Prev, int Now) {
    int L1 = Prev >> 2;
    int L2 = Prev ^ (L1 << 2);
    int A[4] = {0, 0, 0, 0};
    A[L1] = 1, A[L2] = 1, A[Now] = 1;
    return A[1] + A[2] + A[3];
}

int main() {
    scanf("%d", &n);
    scanf("%s", A+1);
    fill(dp[0], dp[0] + 256, -INF);
    dp[0][0] = 0;
    for(int i = 1, pre = 0, now = 1; i <= n; ++i, swap(pre, now)) {
        fill(dp[now], dp[now] + 256, -INF);
        for(int j = 0; j < 256; ++j) {
            int First = j >> 4;
            int Second = j ^ (First << 4);
            int NewFirst = ((First >> 2) | (get(A[i]) << 2)) << 4 | Second;
            int NewSecond = (Second >> 2) | (get(A[i]) << 2) | (First << 4);
            dp[now][NewFirst] = max(dp[now][NewFirst], dp[pre][j] + getCost(First, get(A[i])));
            dp[now][NewSecond] = max(dp[now][NewSecond], dp[pre][j] + getCost(Second, get(A[i])));
        }
        if(i == n) for(int j = 0; j < 256; ++j) Ans = max(Ans, dp[now][j]);
    }
    printf("%d\n", Ans);
}

Compilation message

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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