oj.uz

Submission #970818

# Submission time Handle Problem Language Result Execution time Memory
970818 2024-04-27T10:37:26 Z Ludissey Miners (IOI07_miners) C++17
100 / 100
 795 ms 444772 KB 
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(x) (x).begin(), (x).end()
using namespace std;
vector<int> a;
vector<vector<vector<vector<vector<int>>>>> memo;

int calcExtra(int c, int prev, int prev2){
    if(prev==3) return 1;
    else if(prev2==3){
        if(prev!=c) return 2;
        else return 1;
    }
    if(c!=prev&&prev2!=c&&prev2!=prev) return 3;
    else if(c==prev&&prev2==c) return 1;
    else return 2;
}

int dp(int x, int prev, int prevprev, int prev2, int prevprev2){
    if(x==sz(a)) return 0;
    if(memo[x][prev][prevprev][prev2][prevprev2]!=-1) return memo[x][prev][prevprev][prev2][prevprev2];
    int mine1=dp(x+1,a[x], prev ,prev2,prevprev2)+calcExtra(a[x],prev,prevprev);
    int mine2=dp(x+1,prev,prevprev, a[x], prev2)+calcExtra(a[x],prev2,prevprev2);
    return memo[x][prev][prevprev][prev2][prevprev2]=max(mine1,mine2);
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    a.resize(n);
    memo.resize(n+1, vector<vector<vector<vector<int>>>>(4,vector<vector<vector<int>>>(4, vector<vector<int>>(4, vector<int>(4, -1)))));
    for (int i = 0; i < n; i++) 
    {
        char c; cin >>c;
        if(c=='M') a[i]=0;
        else if(c=='B') a[i]=1;
        else if(c=='F') a[i]=2;
    }
    cout << dp(0,3,3,3,3)<<"\n";
    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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