oj.uz

Submission #547802

# Submission time Handle Problem Language Result Execution time Memory
547802 2022-04-11T19:20:40 Z StrawHatWess Miners (IOI07_miners) C++17
100 / 100
 920 ms 648 KB 
#include <bits/stdc++.h>
using namespace std;

#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define F first
#define S second
#define PB push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
const int maxn = 1e5 + 5;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)

#define dbg(x) cerr << #x << " : " << x << endl; 

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}

//---------------------------------------------

int n, dp[2][10][10];
//unordered_map<string, int> ind;
vi ind(10000); 
vector<string> ind2 = {"", "MM", "MF", "MB", "BB", "BM", "BF", "FF", "FB", "FM", "M", "B", "F"};
string s;

int val(string x, char c) {
    if (x.size() == 2) {
        char a = x[0], b = x[1];
        if (a==b && b == c) return 1;
        if (a != b && b != c && c != a) return 3;
        return 2;
    }
    if (x.size() == 1) {
        char a = x[0];
        if (a == c) return 1;
        return 2;
    }
    return 1;

}

int f(string s){
    int ans=0; 
    for(char c: s){
        ans*=27; 
        ans+=c-'A'+1; 
    }
    return ans;
}


int main() {
    IO(); boost; 

    cin >> n >> s;
    ind[f("")] = 0; 
    ind[f("MM")] = 1; ind[f("MF")] = 2; ind[f("MB")] = 3; 
    ind[f("BB")] = 4; ind[f("BM")] = 5; ind[f("BF")] = 6; 
    ind[f("FF")] = 7; ind[f("FB")] = 8; ind[f("FM")] = 9; 
    ind[f("M")] = 1; ind[f("B")] = 4; ind[f("F")] = 7;
    
    for (int i=n-1; i>=0; i--) {
        for (int j = 0; j<=9; j++) {
            for (int k=0; k<=9; k++) {
                if(!k && !j && i) break; 

                string lstS1, lstS2, nwS1, nwS2;
                lstS1 = ind2[j], lstS2 = ind2[k];
                
                
                if(sz(lstS1)) nwS1 += lstS1.back();
                nwS1 += s[i]; 
                if(sz(lstS2)) nwS2 += lstS2.back(); 
                nwS2 += s[i];
                
                int c1 = dp[(i+1)&1][ind[f(nwS1)]][k] + val(lstS1, s[i]);
                int c2 = dp[(i+1)&1][j][ind[f(nwS2)]] + val(lstS2, s[i]);
               
                dp[i&1][j][k] = max(c1, c2);
            }
        }

    }
    
    cout << dp[0][0][0] << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 340 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 368 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 416 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 608 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 920 ms 648 KB Output is correct