oj.uz

Submission #449684

# Submission time Handle Problem Language Result Execution time Memory
449684 2021-08-02T07:48:38 Z CyberSleeper Miners (IOI07_miners) C++14
100 / 100
 289 ms 114144 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, vis[100007][4][4][4][4], A[100007];
string S, food="MFB", choice[]={"FB", "MB", "MF", "BF", "BM", "FM"};
vector<int> loc[3];
int DP(int loc, int M11, int M12, int M21, int M22){
    if(loc>=N)
        return 0;
    int &ret=vis[loc][M11][M12][M21][M22], cnt=0;
    if(ret==-1){
        bool ada[4]={0, 0, 0, 0};
        ada[M11]=ada[M12]=ada[A[loc]]=1;
        for(int i=0; i<3; i++)
            cnt+=ada[i];
        ret=max(ret, cnt+DP(loc+1, M12, A[loc], M21, M22));

        ada[0]=ada[1]=ada[2]=cnt=0;
        ada[M21]=ada[M22]=ada[A[loc]]=1;
        for(int i=0; i<3; i++)
            cnt+=ada[i];
        ret=max(ret, cnt+DP(loc+1, M11, M12, M22, A[loc]));
    }
    return ret;
}
int main(){
    fastio;
    memset(vis, -1, sizeof(vis));
    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;
                loc[j].pb(i);
            }
        }
    }
    cout << DP(0, 3, 3, 3, 3);
}

Compilation message

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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