oj.uz

Submission #61865

# Submission time Handle Problem Language Result Execution time Memory
61865 2018-07-27T01:52:16 Z updown1 Miners (IOI07_miners) C++17
100 / 100
 112 ms 1632 KB 
/*
dp[loc][prev01][prev00][prev[11][prev10] = max coal
0: None
1: M
2: B
3: F
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define For(i, a, b) for(int i=a; i<b; i++)
#define ffi For(i, 0, N)
#define ffj For(j, 0, K+1)
#define ffa ffi ffj
#define s <<" "<<
#define c <<" : "<<
#define w cout
//#define e "\n"
#define pb push_back
#define mp make_pair
#define a first
#define b second
//#define int ll
//500,000,000 operations
const int MAXN = 100000, INF = 100000000;
//Global Variables
int N, dp[2][4][4][4][4], out, inp[MAXN];
string in;

int cnt(int a, int b, int d) {
    /// make a the smallest
    if (a > b) swap(a, b);
    if (a > d) swap(a, d);
    /// b<d
    if (b>d) swap(b, d);
    if (a == 0 && b == 0 && d == 0) return 0;
    if (a == 0 && b == 0) return 1;
    if (a == 0) return cnt(b, b, d);
    if (a == b && a == d) return 1;
    if (a == b || a == d || b == d) return 2;
    return 3;
}

main() {
    //ifstream cin("test.in");
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N >> in;
    ffi {
        if (in[i] == 'M') inp[i] = 1;
        else if (in[i] == 'B') inp[i] = 2;
        else inp[i] = 3;
    }
    dp[0][0][inp[0]][0][0] = 1;
    /// Push dp
    For (i, 0, N-1) {
        For (d, 0, 4) For (e, 0, 4) For (f, 0, 4) For (g, 0, 4) {
            if (dp[i%2][d][e][f][g] == 0) continue;
            //w<< i s d s e s f s g c dp[i][d][e][f][g]<<endl;
            dp[(i+1)%2][e][inp[i+1]][f][g] = max(dp[(i+1)%2][e][inp[i+1]][f][g], dp[i%2][d][e][f][g] + cnt(d, e, inp[i+1]));
            dp[(i+1)%2][d][e][g][inp[i+1]] = max(dp[(i+1)%2][d][e][g][inp[i+1]], dp[i%2][d][e][f][g] + cnt(f, g, inp[i+1]));
            dp[i%2][d][e][f][g] = 0;
        }
    }
    For (d, 0, 4) For (e, 0, 4) For (f, 0, 4) For (g, 0, 4) {
        out = max(out, dp[(N-1)%2][d][e][f][g]);
    }
    w<< out<<endl;
}

Compilation message

miners.cpp:44:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

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 2 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 2 ms 488 KB Output is correct

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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