oj.uz

답안 #396091

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
396091 2021-04-29T12:49:59 Z Sorting Miners (IOI07_miners) C++17
0 / 100
 1500 ms 15648 KB 
#include <bits/stdc++.h>

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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 332 KB Output isn't correct

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 356 KB Output isn't correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 356 KB Output isn't correct

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 348 KB Output isn't correct

Subtask #5
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 332 KB Output isn't correct

Subtask #6
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 332 KB Output isn't correct

Subtask #7
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 494 ms 4236 KB Output isn't correct

Subtask #8
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1581 ms 13412 KB Time limit exceeded

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1586 ms 14240 KB Time limit exceeded

Subtask #10
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1591 ms 15168 KB Time limit exceeded

Subtask #11
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1592 ms 15556 KB Time limit exceeded

Subtask #12
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1590 ms 15648 KB Time limit exceeded