oj.uz

Submission #918919

# Submission time Handle Problem Language Result Execution time Memory
918919 2024-01-30T18:42:08 Z ThylOne Lamps (JOI19_lamps) C++14
0 / 100
 116 ms 106148 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(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 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 7 ms 23896 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Correct 6 ms 23896 KB Output is correct
8 Correct 6 ms 23896 KB Output is correct
9 Correct 6 ms 23896 KB Output is correct
10 Correct 6 ms 23896 KB Output is correct
11 Correct 7 ms 23896 KB Output is correct
12 Correct 6 ms 23896 KB Output is correct
13 Incorrect 6 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 23900 KB Output is correct
3 Correct 6 ms 23896 KB Output is correct
4 Correct 6 ms 23900 KB Output is correct
5 Correct 7 ms 23896 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Correct 6 ms 23896 KB Output is correct
8 Correct 6 ms 23896 KB Output is correct
9 Correct 6 ms 23896 KB Output is correct
10 Correct 6 ms 23896 KB Output is correct
11 Correct 7 ms 23896 KB Output is correct
12 Correct 6 ms 23896 KB Output is correct
13 Incorrect 6 ms 23896 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.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 6 ms 23944 KB Output is correct
4 Correct 6 ms 23896 KB Output is correct
5 Correct 6 ms 23896 KB Output is correct
6 Correct 6 ms 23900 KB Output is correct
7 Incorrect 116 ms 106148 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

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