oj.uz

Submission #607628

# Submission time Handle Problem Language Result Execution time Memory
607628 2022-07-26T22:00:47 Z Blobo2_Blobo2 Miners (IOI07_miners) C++17
25 / 100
 587 ms 315288 KB 
/*
Editor: Abdelrahman Hossam
Nickname: Blobo2_Blobo2
I love my mama
*/\
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define gen(arr,n,nxt)  generate(arr,arr+n,nxt)
#define Blobo2 ios_base::sync_with_stdio(false);cin.tie(0);

const int mod = 1e9+7;
int nxt(){int x;cin>>x;return x;}

int dp[100000][28][28],n;
string s;
int mask3[4][4][4];
int mask1[3], mask2[3];
int solve(int idx=0){
    if(idx == n)
        return 0;
    int m1 = mask3[mask1[0]][mask1[1]][mask1[2]];
    int m2 = mask3[mask2[0]][mask2[1]][mask2[2]];
    int &ret = dp[idx][m1][m2];
    if(~ret)return ret;

    int meal = 0;
    if(s[idx] == 'M')meal = 1;
    if(s[idx] == 'B')meal = 2;
    if(s[idx] == 'F')meal = 4;

    int x = mask1[0];
    swap(mask1[0],mask1[1]);
    swap(mask1[2],mask1[1]);
    mask1[2] = (meal/2)+1;

    int c=0;
    if((mask1[0] == mask1[1] && mask1[1] == mask1[2] && mask1[0] && mask1[1] && mask1[2]) || (mask1[2] && !mask1[1]))c=1;
    else if(((mask1[0] == mask1[1]) 
        ||  (mask1[0] == mask1[2])
        ||  (mask1[1] == mask1[2]))
        &&   mask1[0] && mask1[1] && mask1[2])c = 2;
    else if(mask1[0] == 0 && mask1[1] == mask1[2])c = 1;
    else if(mask1[0] == 0 && mask1[1] != mask1[2])c = 2;
    else if(mask1[0] && mask1[1] && mask1[2])c=3;
    ret = solve(idx+1) + c;

    swap(mask1[2],mask1[1]);
    swap(mask1[0],mask1[1]);
    mask1[0] = x;

    x = mask2[0];
    swap(mask2[0],mask2[1]);
    swap(mask2[2],mask2[1]);
    mask2[2] = (meal/2)+1;

    c=0;
    if((mask2[0] == mask2[1] && mask2[1] == mask2[2] && mask2[0] && mask2[1] && mask2[2]) || (mask2[2] && !mask2[1]))c=1;
    else if(((mask2[0] == mask2[1]) 
        ||  (mask2[0] == mask2[2])
        ||  (mask2[1] == mask2[2]))
        &&   mask2[0] && mask2[1] && mask2[2])c = 2;
    else if(mask2[0] == 0 && mask2[1] == mask2[2])c = 1;
    else if(mask2[0] == 0 && mask2[1] != mask2[2])c = 2;
    else if(mask2[0] && mask2[1] && mask2[2])c=3;
    ret = max(ret,solve(idx+1) + c);

    swap(mask2[2],mask2[1]);
    swap(mask2[0],mask2[1]);
    mask2[0] = x;

    return ret;
}

signed main() {
    Blobo2
    n=nxt();
    cin>>s;
    memset(dp,-1,sizeof dp);
    int idx=1;
    for(int A=0;A<4;A++){
        for(int B=0;B<4;B++){   
            for(int C=0;C<4;C++){
                mask3[A][B][C] = idx++;
            }
        }
    }
    cout<<solve();
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 307064 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

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

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 124 ms 307116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 116 ms 307060 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
7.0 / 7.0

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

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 139 ms 307148 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 307532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 308068 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 275 ms 309188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 295 ms 313380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 587 ms 315288 KB Output isn't correct
2 Halted 0 ms 0 KB -