oj.uz

Submission #919108

# Submission time Handle Problem Language Result Execution time Memory
919108 2024-01-31T10:07:29 Z ThylOne Lamps (JOI19_lamps) C++14
4 / 100
 149 ms 106256 KB 
    //####################
    //LAMP-JOI2019
    //####################
    #include<bits/stdc++.h>
     
    using namespace std;
    int n;
    string a,b;
    const int RIEN = 0;
    const int FLIP = 1;
    const int ZERO = 2;
    const int ONE = 3;
    const int ONE_ZERO = 4;
    const int ZERO_ONE = 5;
    const int maxiNode = 1000000;
    int dp[maxiNode][6];
    int solve(int pos,int state){
        if(pos<n && dp[pos][state]!=-1)return dp[pos][state];
        if(pos==n){
            return 0;
        }else{
            int ans = n+1;
            if(state==RIEN){
                ans = min(ans,1+solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }else if(state == FLIP){
                ans = min(ans, solve(pos+1,FLIP) + (b[pos]==a[pos]?n+1:0));
                ans = min(ans,1+solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
            }else if(state == ZERO){
                ans = min(ans,solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,ZERO_ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }else if(state == ONE){
                ans = min(ans,solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,ONE_ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            
            }else if(state == ZERO_ONE){
                ans = min(ans,solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,solve(pos+1,ZERO_ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }else if(state==ONE_ZERO){
                ans = min(ans,solve(pos+1,ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,solve(pos+1,ONE)+(b[pos]=='0'?n+1:0));
                ans = min(ans,solve(pos+1,ONE_ZERO)+(b[pos]=='1'?n+1:0));
                ans = min(ans,1+solve(pos+1,FLIP)+(b[pos]==a[pos]?n+1:0));
            }
            if(a[pos]==b[pos]){
                ans=min(ans, solve(pos+1,RIEN));
            }
            return dp[pos][state]=ans;
        }
    }
    signed main(){
        for(int i = 0;i<maxiNode;i++){
            for(int j = 0;j<6;j++){
                dp[i][j] = -1;
            }
        }
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        cin>>a>>b;
        cout<<solve(0,RIEN)<<endl;
        return 0;
        };

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Correct 6 ms 23896 KB Output is correct
3 Correct 5 ms 23896 KB Output is correct
4 Correct 6 ms 23896 KB Output is correct
5 Correct 7 ms 23896 KB Output is correct
6 Correct 6 ms 23896 KB Output is correct
7 Correct 6 ms 23904 KB Output is correct
8 Correct 6 ms 23900 KB Output is correct
9 Correct 6 ms 23896 KB Output is correct
10 Correct 6 ms 23896 KB Output is correct
11 Correct 6 ms 23896 KB Output is correct
12 Correct 5 ms 23896 KB Output is correct
13 Incorrect 5 ms 23896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Correct 6 ms 23896 KB Output is correct
3 Correct 5 ms 23896 KB Output is correct
4 Correct 6 ms 23896 KB Output is correct
5 Correct 7 ms 23896 KB Output is correct
6 Correct 6 ms 23896 KB Output is correct
7 Correct 6 ms 23904 KB Output is correct
8 Correct 6 ms 23900 KB Output is correct
9 Correct 6 ms 23896 KB Output is correct
10 Correct 6 ms 23896 KB Output is correct
11 Correct 6 ms 23896 KB Output is correct
12 Correct 5 ms 23896 KB Output is correct
13 Incorrect 5 ms 23896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23896 KB Output is correct
2 Correct 5 ms 23896 KB Output is correct
3 Correct 5 ms 23900 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 5 ms 23896 KB Output is correct
6 Correct 6 ms 23896 KB Output is correct
7 Correct 149 ms 106144 KB Output is correct
8 Correct 130 ms 106140 KB Output is correct
9 Correct 131 ms 106148 KB Output is correct
10 Correct 133 ms 106256 KB Output is correct
11 Correct 132 ms 106148 KB Output is correct
12 Correct 122 ms 106256 KB Output is correct
13 Correct 136 ms 106248 KB Output is correct
14 Correct 136 ms 106148 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 23896 KB Output is correct
2 Correct 6 ms 23896 KB Output is correct
3 Correct 5 ms 23896 KB Output is correct
4 Correct 6 ms 23896 KB Output is correct
5 Correct 7 ms 23896 KB Output is correct
6 Correct 6 ms 23896 KB Output is correct
7 Correct 6 ms 23904 KB Output is correct
8 Correct 6 ms 23900 KB Output is correct
9 Correct 6 ms 23896 KB Output is correct
10 Correct 6 ms 23896 KB Output is correct
11 Correct 6 ms 23896 KB Output is correct
12 Correct 5 ms 23896 KB Output is correct
13 Incorrect 5 ms 23896 KB Output isn't correct
14 Halted 0 ms 0 KB -