oj.uz

Submission #256948

# Submission time Handle Problem Language Result Execution time Memory
256948 2020-08-03T12:41:57 Z someone Miners (IOI07_miners) C++14
100 / 100
 476 ms 402040 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5, POS = 256, INF = 1e9;

int n, f[N], val[N][POS];

signed main() {
    /*
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    */
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin >> n;
    for(int i = 0; i < n; i++) {
        char c; cin >> c;
        if(c == 'M') f[i] = 1;
        if(c == 'F') f[i] = 2;
        if(c == 'B') f[i] = 3;
    }
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < POS; j++)
            val[i][j] = -INF;
    val[0][0] = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < POS; j++) {
            int p[4], sit = j;
            for(int k = 0; k < 4; k++, sit /= 4)
                p[k] = sit % 4;
            int t1 = 1, t2 = 1;
            if(f[i] != p[0] && p[0] != 0) t1++;
            if(f[i] != p[2] && p[2] != 0) t2++;
            if(f[i] != p[1] && p[0] != p[1] && p[1] != 0) t1++;
            if(f[i] != p[3] && p[2] != p[3] && p[3] != 0) t2++;
            
            int j1 = p[1] + 4*f[i] + 16*p[2] + 64*p[3],
                j2 = p[0] + 4*p[1] + 16*p[3] + 64*f[i];
            val[i+1][j1] = max(val[i+1][j1], val[i][j] + t1);
            val[i+1][j2] = max(val[i+1][j2], val[i][j] + t2);
        }
    }
    int maxi = 0;
    for(int j = 0; j < POS; j++)
        maxi = max(maxi, val[n][j]);
    cout << maxi;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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