oj.uz

Submission #483171

# Submission time Handle Problem Language Result Execution time Memory
483171 2021-10-28T02:38:50 Z phamhoanghiep Lamps (JOI19_lamps) C++17
4 / 100
 77 ms 30936 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
string st;
string en;
int mask[maxn]; // 0: 0, 1: 1, 2: f, 3: 0f, 4: 1f, 5: nothing
int dp[maxn][6];
int n;
signed main() {
    cin>>n;
    cin>>st>>en;
    st=' '+st;
    en=' '+en;
    for(int i=1 ; i<=n ; i++) {
        if(st[i]!=en[i]) mask[i]+=(1<<2);
        if(en[i]=='0') mask[i]+=(1<<4)+(1<<0);
        if(en[i]=='1') mask[i]+=(1<<1)+(1<<3);
        dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=dp[i][4]=dp[i][5]=n+1;
    }
    dp[0][0]=dp[0][1]=dp[0][2]=1; dp[0][3]=dp[0][4]=2; dp[0][5]=0;
    for(int i=1 ; i<=n ; i++) {
        if(en[i]=='0') {
            // 0 or 1f
            dp[i][0]=min({dp[i-1][0],dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+1});
            dp[i][3]=min({dp[i-1][0]+1,dp[i-1][1]+2,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+2});
        }
        else {
            dp[i][1]=min({dp[i-1][0]+1,dp[i-1][1],dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+1});
            dp[i][4]=min({dp[i-1][0]+2,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+2});
        }
        if(en[i]!=st[i]) {
            dp[i][2]=min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2],dp[i-1][3],dp[i-1][4],dp[i-1][5]+1});
        }
        else dp[i][5]=min({dp[i-1][0],dp[i-1][1],dp[i-1][2],dp[i-1][3],dp[i-1][4],dp[i-1][5]});
    }
    cout<<min({dp[n][0],dp[n][1],dp[n][2],dp[n][3],dp[n][4],dp[n][5]});
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 0 ms 300 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 0 ms 300 KB Output is correct
16 Incorrect 1 ms 204 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 0 ms 204 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 65 ms 30840 KB Output is correct
8 Correct 68 ms 30860 KB Output is correct
9 Correct 77 ms 30856 KB Output is correct
10 Correct 68 ms 30848 KB Output is correct
11 Correct 68 ms 30936 KB Output is correct
12 Correct 70 ms 30840 KB Output is correct
13 Correct 67 ms 30864 KB Output is correct
14 Correct 65 ms 30892 KB Output is correct

Subtask #4
0 / 49.0

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