oj.uz

Submission #547796

# Submission time Handle Problem Language Result Execution time Memory
547796 2022-04-11T18:50:59 Z StrawHatWess Miners (IOI07_miners) C++17
84 / 100
 1500 ms 468 KB 
#include <bits/stdc++.h>
using namespace std;

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][14][14];
//unordered_map<string, int> ind;
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 && c == a) 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;
        else return 2;
    }
    return 1;

}

int ind(string s){
    if(s=="") return 0;
    if(s=="MM") return 1;
    if(s=="MF") return 2;
    if(s=="MB") return 3;
    if(s=="BB") return 4;
    if(s=="BM") return 5;
    if(s=="BF") return 6;
    if(s=="FF") return 7;
    if(s=="FB") return 8;
    if(s=="FM") return 9;
    if(s=="M") return 10;
    if(s=="B") return 11;
    if(s=="F") return 12;
}


int main() {
    IO(); 

    cin >> n >> s;
    /*ind[""] = 0; 
    ind["MM"] = 1; ind["MF"] = 2; ind["MB"] = 3; 
    ind["BB"] = 4; ind["BM"] = 5; ind["BF"] = 6; 
    ind["FF"] = 7; ind["FB"] = 8; ind["FM"] = 9; 
    ind["M"] = 10; ind["B"] = 11; ind["F"] = 12;*/
    
    for (int i=n-1; i>=0; i--) {
        for (int j = 0; j <= 12; j++) {
            for (int k=0; k <=12; k++) {
                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(nwS1)][k] + val(lstS1, s[i]);
                int c2 = dp[(i+1)&1][j][ind(nwS2)] + val(lstS2, s[i]);
               
                dp[i%2][j][k] = max(c1, c2);
            }
        }

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

Compilation message

miners.cpp: In function 'int ind(std::string)':
miners.cpp:62:1: warning: control reaches end of non-void function [-Wreturn-type]
   62 | }
      | ^

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1596 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1557 ms 468 KB Time limit exceeded
2 Halted 0 ms 0 KB -