oj.uz

Submission #449873

# Submission time Handle Problem Language Result Execution time Memory
449873 2021-08-02T08:51:27 Z CyberSleeper Miners (IOI07_miners) C++14
100 / 100
 185 ms 896 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[2][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 n=0; n<N; n++)
        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[n%2][i][j][k][l], nxt=(n+1)%2;
                        if(now==-1)
                            continue;
                        bool ada[4]={0, 0, 0, 0};
                        ada[i]=ada[j]=ada[A[n]]=1;
                        for(int ii=0; ii<3; ii++)
                            cnt+=ada[ii];
                        int &ret1=DP[nxt][j][A[n]][k][l];
                        ret1=max(ret1, cnt+now);

                        ada[0]=ada[1]=ada[2]=cnt=0;
                        ada[k]=ada[l]=ada[A[n]]=1;
                        for(int ii=0; ii<3; ii++)
                            cnt+=ada[ii];
                        int &ret2=DP[nxt][i][j][l][A[n]];
                        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%2][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 1 ms 204 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 376 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 460 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 780 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 896 KB Output is correct