oj.uz

Submission #54603

# Submission time Handle Problem Language Result Execution time Memory
54603 2018-07-04T07:51:42 Z imeimi2000 Miners (IOI07_miners) C++17
100 / 100
 87 ms 704 KB 
#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

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.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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