oj.uz

Submission #530753

# Submission time Handle Problem Language Result Execution time Memory
530753 2022-02-26T16:54:27 Z perchuts Miners (IOI07_miners) C++17
17 / 100
 1500 ms 844 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; }

map<pair<string,string>,int>dp[2];
map<pair<string,string>,bool>mark,mark2;
int main(){_
    int n;cin>>n;
    string s;cin>>s;
    mark[{"",""}]=1;
    for(int i=1;i<=n;++i){
        for(auto [p,z]:mark){
            auto [x,y] = p;
            int b = dp[(i-1)&1][{x,y}];
            int j = max(0,sz(x)-2),cntm=0,cntf=0,cntb=0;
            string newa,newb;
            while(j<sz(x))newa+=x[j++]; 
            newa+=s[i];
            for(auto u:newa){
                cntm|=u=='M',cntf|=u=='F',cntb|=u=='B';
            }
            if(!mark2[{newa,y}])mark2[{newa,y}] = 1,dp[i&1][{newa,y}] = b+cntm+cntf+cntb;
            else ckmax(dp[i&1][{newa,y}],b+cntm+cntb+cntf);
            j = max(0,sz(y)-2), cntm = cntf = cntb = 0;
            while(j<sz(y))newb+=y[j++];
            newb+=s[i];
            for(auto u:newb){
                cntm|=u=='M',cntf|=u=='F',cntb|=u=='B';
            }
            if(!mark2[{x,newb}])mark2[{x,newb}]=1,dp[i&1][{x,newb}] = b+cntm+cntf+cntb;
            else ckmax(dp[i&1][{x,newb}],b+cntm+cntb+cntf);
        }
        mark = mark2;mark2.clear();
    }
    int ans = 0;
    for(auto [a,b]:dp[n&1])ckmax(ans,b);
    cout<<ans<<endl; 
};

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
9.0 / 9.0

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

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
8.0 / 8.0

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

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1583 ms 644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1584 ms 628 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1591 ms 720 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1585 ms 844 KB Time limit exceeded
2 Halted 0 ms 0 KB -