Submission #396094

#	Time	Username	Problem	Language	Result	Execution time	Memory
396094		Sorting	Miners (IOI07_miners)	C++17	100 / 100	129 ms	844 KiB

miners

#include <bits/stdc++.h>
#pragma GCC optimize("O3")

using namespace std;

const int N = 1e5 + 3;
template<class T> void check_max(T &a, const T b){ a = (a > b) ? a : b; }

int dp[2][16][16];
int n, a[N];
string s;

int calc_points(int t1, int t2, int t3){
    if(t1 == 0) t1 = t3;
    if(t2 == 0) t2 = t3;
    if(t1 == t2  && t2 == t3) return 1;
    if(t1 == t2 || t1 == t3 || t2 == t3) return 2;
    return 3;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> s;
    for(int i = 0; i < n; ++i){
        if(s[i] == 'M') a[i] = 1;
        else if(s[i] == 'F') a[i] = 2;
        else a[i] = 3;
    }

    for(int i = n - 1; i >= 0; --i){
        int c_idx = (i & 1), next_idx = ((i + 1) & 1);
        for(int m1 = 0; m1 < 16; ++m1){
            for(int m2 = 0; m2 < 16; ++m2){
                int &ans = dp[c_idx][m1][m2];
                ans = 0;

                int t1, t2, t3;
                t1 = m1 / 4, t2 = m1 % 4, t3 = a[i];
                check_max(ans, calc_points(t1, t2, t3) + dp[next_idx][(m1 % 4) * 4 + a[i]][m2]);

                t1 = m2 / 4, t2 = m2 % 4, t3 = a[i];
                check_max(ans, calc_points(t1, t2, t3) + dp[next_idx][(m2 % 4) * 4 + a[i]][m1]);
                //cout << ans << " - " << i << " " << m1 << " " << m2 << endl; 
            }
        }
    }

    cout << dp[0][0][0] << "\n";
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 8 / 8