oj.uz

Submission #59560

# Submission time Handle Problem Language Result Execution time Memory
59560 2018-07-22T10:33:39 Z Autoratch Miners (IOI07_miners) C++14
100 / 100
 371 ms 1456 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define MOD 1e9 + 7

int n,dp[2][4][4][4][4],a[100000],then = 0,now = 1,ans;
string s;

int uni(int x,int y,int z)
{
    int val = 0;
    if(x==1 or y==1 or z==1) val++;
    if(x==2 or y==2 or z==2) val++;
    if(x==3 or y==3 or z==3) val++;
    return val;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    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 xl = 0;xl < 4;xl++) for(int xr = 0;xr < 4;xr++) for(int yl = 0;yl < 4;yl++) for(int yr = 0;yr < 4;yr++)
    {
        dp[then][xl][xr][yl][yr] = INT_MIN;
        dp[now][xl][xr][yl][yr] = INT_MIN;
    }

    dp[then][0][a[0]][0][0] = 1;
    dp[then][0][0][0][a[0]] = 1;

    for(int i = 1;i < n;i++)
    {
        for(int xl = 0;xl < 4;xl++) for(int xr = 0;xr < 4;xr++) for(int yl = 0;yl < 4;yl++) for(int k = 0;k < 4;k++)
            dp[now][xl][xr][yl][a[i]] = max(dp[now][xl][xr][yl][a[i]],dp[then][xl][xr][k][yl]+uni(a[i],yl,k));
        for(int yl = 0;yl < 4;yl++) for(int yr = 0;yr < 4;yr++) for(int xl = 0;xl < 4;xl++) for(int k = 0;k < 4;k++)
            dp[now][xl][a[i]][yl][yr] = max(dp[now][xl][a[i]][yl][yr],dp[then][k][xl][yl][yr]+uni(a[i],xl,k));
        swap(then,now);
    }

    for(int xl = 0;xl < 4;xl++) for(int xr = 0;xr < 4;xr++) for(int yl = 0;yl < 4;yl++) for(int yr = 0;yr < 4;yr++) ans = max(ans,dp[then][xl][xr][yl][yr]);

    cout << ans;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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