Submission #234787

#	Time	Username	Problem	Language	Result	Execution time	Memory
234787		nicolaalexandra	Miners (IOI07_miners)	C++14	100 / 100	141 ms	100728 KiB

miners

#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 (stderr)

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

• 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