oj.uz

Submission #376161

# Submission time Handle Problem Language Result Execution time Memory
376161 2021-03-11T02:43:08 Z jass921026 Lamps (JOI19_lamps) C++14
4 / 100
 48 ms 5968 KB 
#include<bits/stdc++.h>
using namespace std;
#define jizz ios_base::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef pair<int,int> pii;
#define F first
#define S second
#define ALL(x) (x).begin(),(x).end()
const int MAXN=1E6+10, INF=1E9;
int dp[2][2][3];
bool a[MAXN], b[MAXN];
int GetMV(int x, int y){
    int res=INF;
    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++){
            int tmp=dp[0][i][j];
            if(x>0&&i!=x) tmp++;
            if(y>0&&j!=y) tmp++;
            res=min(res,tmp);
        }
    }
    return res;
}
int main(){ jizz
    int n;
    cin>>n;
    string sa, sb;
    cin>>sa>>sb;
    for(int i=0;i<n;i++){
        a[i+1]=sa[i]-'0';
        b[i+1]=sb[i]-'0';
    }
    dp[0][1][0]=dp[0][0][1]=dp[0][1][1]=dp[0][0][2]=dp[0][1][2]=INF;
    for(int i=1;i<=n;i++){
        if(a[i]==b[i]) dp[1][0][0]=GetMV(0,0);
        else dp[1][0][0]=INF;
        if(a[i]!=b[i]) dp[1][1][0]=GetMV(1,0);
        else dp[1][1][0]=INF;
        if(b[i]==0) dp[1][0][1]=GetMV(0,1);
        else dp[1][0][1]=INF;
        if(b[i]==0) dp[1][1][1]=GetMV(1,1);
        else dp[1][1][1]=INF;
        if(b[i]==1) dp[1][0][2]=GetMV(0,2);
        else dp[1][0][2]=INF;
        if(b[i]==1) dp[1][1][2]=GetMV(1,2);
        else dp[1][1][2]=INF;
        for(int j=0;j<2;j++){
            for(int k=0;k<3;k++){
                dp[0][j][k]=dp[1][j][k];
            }
        }
    }
    cout<<GetMV(0,0)<<"\n";
    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

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

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 47 ms 5564 KB Output is correct
8 Correct 45 ms 5692 KB Output is correct
9 Correct 45 ms 5948 KB Output is correct
10 Correct 46 ms 5968 KB Output is correct
11 Correct 45 ms 5948 KB Output is correct
12 Correct 45 ms 5948 KB Output is correct
13 Correct 44 ms 5948 KB Output is correct
14 Correct 48 ms 5968 KB Output is correct

Subtask #4
0 / 49.0

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