Submission #54603

#	Time	Username	Problem	Language	Result	Execution time	Memory
54603		imeimi2000	Miners (IOI07_miners)	C++17	100 / 100	87 ms	704 KiB

miners

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 1e8;
int tr[256];
int dp1[16][16];
int dp2[16][16];
int nxt[16][4];
int cnt[16][4];

pii getCoal(int x, int p) {
    static int cnt[4];
    cnt[1] = cnt[2] = cnt[3] = 0;
    int nxt = (x << 2 | p) & 15;
    cnt[p] = 1;
    cnt[x & 3] = 1;
    cnt[x >> 2] = 1;
    return pii(nxt, cnt[1] + cnt[2] + cnt[3]);
}

int imax(int x, int y) {
    return x < y ? y : x;
}

int n;
char str[100001];
int main() {
    tr['M'] = 1;
    tr['F'] = 2;
    tr['B'] = 3;
    
    for (int i = 0; i < 16; ++i) {
        for (int j = 1; j <= 3; ++j) {
            tie(nxt[i][j], cnt[i][j]) = getCoal(i, j);
        }
    }
    
    scanf("%d%s", &n, str);
    for (int i = 0; i < 16; ++i) {
        for (int j = 0; j < 16; ++j) {
            dp1[i][j] = -inf;
            dp2[i][j] = -inf;
        }
    }
    dp1[0][0] = 0;
    
    for (int it = 0; it < n; ++it) {
        int i = tr[str[it]];
        for (int j = 0; j < 16; ++j) {
            for(int k = 0; k < 16; ++k) {
                if (dp1[j][k] < 0) continue;
                dp2[nxt[j][i]][k] = imax(dp2[nxt[j][i]][k], dp1[j][k] + cnt[j][i]);
                
                dp2[j][nxt[k][i]] = imax(dp2[j][nxt[k][i]], dp1[j][k] + cnt[k][i]);
            }
        }
        for (int j = 0; j < 16; ++j) {
            for (int k = 0; k < 16; ++k) {
                dp1[j][k] = dp2[j][k];
                dp2[j][k] = -inf;
            }
        }
    }
    
    int ans = 0;
    for (int i = 0; i < 16; ++i) {
        for (int j = 0; j < 16; ++j) {
            ans = imax(ans, dp1[i][j]);
        }
    }
    printf("%d\n", ans);
    
	return 0;
}

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:65:27: warning: array subscript has type 'char' [-Wchar-subscripts]
         int i = tr[str[it]];
                           ^
miners.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%s", &n, str);
     ~~~~~^~~~~~~~~~~~~~~~~

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