oj.uz

Submission #234787

# Submission time Handle Problem Language Result Execution time Memory
234787 2020-05-25T14:57:16 Z nicolaalexandra Miners (IOI07_miners) C++14
100 / 100
 141 ms 100728 KB 
#include <bits/stdc++.h>
#define DIM 100010
#define INF 2000000000
using namespace std;
int dp[DIM][4][4][4][4];
char v[DIM];
int n,i,nr;
int main (){

    //ifstream cin ("date.in");
   // ofstream cout ("date.out");

    cin>>n>>v+1;

    for (i=0;i<=n;i++)
        for (int val=0;val<=3;val++)
            for (int val2=0;val2<=3;val2++)
                for (int val3=0;val3<=3;val3++)
                    for (int val4=0;val4<=3;val4++)
                        dp[i][val][val2][val3][val4] = -INF;

    dp[0][0][0][0][0] = 0;

    for (i=0;i<n;i++){
        if (v[i+1] == 'M')
            nr = 1;
        else {
            if (v[i+1] == 'F')
                nr = 2;
            else nr = 3;
        }

        for (int val=0;val<=3;val++)
            for (int val2=0;val2<=3;val2++)
                for (int val3=0;val3<=3;val3++)
                    for (int val4=0;val4<=3;val4++){
                        if (dp[i][val][val2][val3][val4] == -INF)
                            continue;

                        /// pun in mina 1
                        int cnt = 0;
                        if (val == 1 || val2 == 1 || nr == 1)
                            cnt++;
                        if (val == 2 || val2 == 2 || nr == 2)
                            cnt++;
                        if (val == 3 || val2 == 3 || nr == 3)
                            cnt++;

                        dp[i+1][val2][nr][val3][val4] = max (dp[i+1][val2][nr][val3][val4], dp[i][val][val2][val3][val4] + cnt);

                        /// pun in mina 2
                        cnt = 0;
                        if (val3 == 1 || val4 == 1 || nr == 1)
                            cnt++;
                        if (val3 == 2 || val4 == 2 || nr == 2)
                            cnt++;
                        if (val3 == 3 || val4 == 3 || nr == 3)
                            cnt++;

                        dp[i+1][val][val2][val4][nr] = max (dp[i+1][val][val2][val4][nr], dp[i][val][val2][val3][val4] + cnt);
                    }}

    int sol = 0;
    for (int val=0;val<=3;val++)
        for (int val2=0;val2<=3;val2++)
            for (int val3=0;val3<=3;val3++)
                for (int val4=0;val4<=3;val4++)
                    sol = max (sol,dp[n][val][val2][val3][val4]);
    cout<<sol;

    return 0;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:13:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin>>n>>v+1;
             ~^~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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