oj.uz

Submission #530763

# Submission time Handle Problem Language Result Execution time Memory
530763 2022-02-26T17:17:53 Z perchuts Miners (IOI07_miners) C++17
100 / 100
 468 ms 371628 KB 
#include <bits/stdc++.h>
#define maxn (int)(1e5+51)
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define ll long long
#define pb push_back
#define ull unsigned long long
#define ii pair<int,int>
#define iii tuple<int,int,int>
#define inf 2000000001
#define mod 1000000007 //998244353
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
int n,pos[maxn],dp[maxn][3][3][3][3][3][3];
bool mark[maxn][3][3][3][3][3][3];
string s;

int solve(int i,int x1,int x2,int x3,int x4,int x5,int x6){
    if(i==n)return 0;
    if(mark[i][x1][x2][x3][x4][x5][x6])return dp[i][x1][x2][x3][x4][x5][x6];
    mark[i][x1][x2][x3][x4][x5][x6] = 1;

    bool d[3]={0,0,0};
    if(x3)d[x1]=1;
    if(x3>1)d[x2]=1;
    d[pos[i]] = 1;
    int delta = d[0]+d[1]+d[2];
    ckmax(dp[i][x1][x2][x3][x4][x5][x6],solve(i+1,pos[i],x1,min(x3+1,2),x4,x5,x6)+delta);

    d[0] = d[1] = d[2] = delta = 0;
    if(x6)d[x4]=1;
    if(x6>1)d[x5]=1;
    d[pos[i]] = 1;
    delta = d[0]+d[1]+d[2];
    ckmax(dp[i][x1][x2][x3][x4][x5][x6],solve(i+1,x1,x2,x3,pos[i],x4,min(x6+1,2))+delta);
    return dp[i][x1][x2][x3][x4][x5][x6];
}


int main(){_
    cin>>n>>s;
    for(int i=0;i<n;++i){
        if(s[i]=='M')pos[i]=0;
        else if(s[i]=='B')pos[i]=1;
        else pos[i]=2;
    }
    cout<<solve(0,0,0,0,0,0,0)<<endl;
}

Compilation message

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

Subtask #1
9.0 / 9.0

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

Subtask #2
9.0 / 9.0

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

Subtask #3
9.0 / 9.0

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

Subtask #4
9.0 / 9.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
7.0 / 7.0

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

Subtask #7
8.0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
8.0 / 8.0

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

Subtask #10
8.0 / 8.0

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

Subtask #11
8.0 / 8.0

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

Subtask #12
8.0 / 8.0

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