oj.uz

Submission #449858

# Submission time Handle Problem Language Result Execution time Memory
449858 2021-08-02T08:45:47 Z CyberSleeper Miners (IOI07_miners) C++14
100 / 100
 127 ms 101100 KB 
#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ull         unsigned long long
#define ld          long double
#define pld         pair<ld, ld>
#define pli         pair<ld, int>
#define pii         pair<int, int>
#define pis         pair<int, string>
#define pl          pair<ll, ll>
#define nl          '\n'
using namespace std;
int N, DP[100007][4][4][4][4], A[100007];
string S, food="MFB";
int main(){
    fastio;
    memset(DP, -1, sizeof(DP));
    cin >> N >> S;
    for(int i=0; i<N; i++)
        for(int j=0; j<3; j++)
            if(S[i]==food[j])
                A[i]=j;

    DP[0][3][3][3][3]=0;
    int ans=0;
    for(int loc=0; loc<N; loc++)
        for(int i=3; i>=0; i--)
            for(int j=3; j>=0; j--)
                for(int k=3; k>=0; k--)
                    for(int l=3; l>=0; l--){
                        int cnt=0, now=DP[loc][i][j][k][l];
                        if(now==-1)
                            continue;
                        bool ada[4]={0, 0, 0, 0};
                        ada[i]=ada[j]=ada[A[loc]]=1;
                        for(int ii=0; ii<3; ii++)
                            cnt+=ada[ii];
                        int &ret1=DP[loc+1][j][A[loc]][k][l];
                        ret1=max(ret1, cnt+now);

                        ada[0]=ada[1]=ada[2]=cnt=0;
                        ada[k]=ada[l]=ada[A[loc]]=1;
                        for(int ii=0; ii<3; ii++)
                            cnt+=ada[ii];
                        int &ret2=DP[loc+1][i][j][l][A[loc]];
                        ret2=max(ret2, cnt+now);
                    }

    for(int i=0; i<4; i++)
        for(int j=0; j<4; j++)
            for(int k=0; k<4; k++)
                for(int l=0; l<4; l++)
                    ans=max(ans, DP[N][i][j][k][l]);
    cout << ans << nl;
}

Compilation message

miners.cpp: In function 'int main()':
miners.cpp:46:49: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |                         ada[0]=ada[1]=ada[2]=cnt=0;
      |                                              ~~~^~

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 100484 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 100584 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 100400 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 100460 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 100404 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 100428 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 100492 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 100504 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 100656 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 100984 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 101100 KB Output is correct