Submission #52166

#	Time	Username	Problem	Language	Result	Execution time	Memory
52166		win11905	Miners (IOI07_miners)	C++11	76 / 100	1591 ms	616 KiB

miners

#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);
    set<int> S; S.emplace(Now), S.emplace(L1), S.emplace(L2);
    if(S.find(0) != S.end()) S.erase(0);
    return (int)S.size(); 
}

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 (stderr)

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