oj.uz

Submission #206596

# Submission time Handle Problem Language Result Execution time Memory
206596 2020-03-04T07:37:14 Z egekabas Lamps (JOI19_lamps) C++14
4 / 100
 37 ms 24012 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n;
int a[1000009];
int b[1000009];
int same[1000009];
int dp[1000009][2];
string s1, s2;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> s1 >> s2;
    for(int i = 1; i <= n; ++i)
        a[i] = (s1[i-1]-'0');
    for(int i = 1; i <= n; ++i)
        b[i] = (s2[i-1]-'0');
    for(int i = 1; i <= n; ++i){
        if(i != 1 && b[i-1] == b[i])
            same[i] = same[i-1];
        else
            same[i] = i;
        dp[i][0] = dp[i][1] = 1e9;
    }
    for(int i = 1; i <= n; ++i){

        if(a[i] == b[i]){
            dp[i][0] = min(dp[i][0], dp[i-1][0]);
            dp[i][1] = min(dp[i][1], 1+min(dp[i-1][1],dp[i-1][0]));
        }
        else{
            dp[i][0] = min(dp[i][0], 1+dp[i-1][0]);
            dp[i][1] = min(dp[i][1], min(dp[i-1][1],dp[i-1][0]));
        }
        dp[i][0] = min(dp[i][0], dp[same[i]-1][0]+1);
        dp[i][1] = min(dp[i][1], min(dp[same[i]-1][1], dp[same[i]-1][0])+1);
        
        dp[i][1] = min(dp[i][1], dp[i][0]+1);
        dp[i][0] = min(dp[i][0], dp[i][1]+1);
        //cout << i << ' ' << dp[i][0] << ' ' << dp[i][1] << '\n';
    }
    cout << dp[n][0] << '\n';
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 380 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct
11 Correct 5 ms 376 KB Output is correct
12 Correct 5 ms 376 KB Output is correct
13 Correct 5 ms 376 KB Output is correct
14 Correct 5 ms 376 KB Output is correct
15 Correct 5 ms 376 KB Output is correct
16 Incorrect 5 ms 376 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 5 ms 376 KB Output is correct
2 Correct 5 ms 380 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 35 ms 23912 KB Output is correct
8 Correct 35 ms 24012 KB Output is correct
9 Correct 35 ms 24008 KB Output is correct
10 Correct 36 ms 24004 KB Output is correct
11 Correct 36 ms 24008 KB Output is correct
12 Correct 37 ms 23880 KB Output is correct
13 Correct 37 ms 24008 KB Output is correct
14 Correct 36 ms 24008 KB Output is correct

Subtask #4
0 / 49.0

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