oj.uz

Submission #206599

# Submission time Handle Problem Language Result Execution time Memory
206599 2020-03-04T07:40:29 Z egekabas Lamps (JOI19_lamps) C++14
4 / 100
 45 ms 41548 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<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n;
ll a[1000009];
ll b[1000009];
ll same[1000009];
ll 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(ll i = 1; i <= n; ++i)
        a[i] = (s1[i-1]-'0');
    for(ll i = 1; i <= n; ++i)
        b[i] = (s2[i-1]-'0');
    for(ll 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] = 1e18;
    }
    for(ll 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 380 KB Output is correct
6 Correct 5 ms 352 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 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 6 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 380 KB Output is correct
6 Correct 5 ms 352 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 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 6 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 376 KB Output is correct
3 Correct 6 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 4 ms 376 KB Output is correct
7 Correct 45 ms 41544 KB Output is correct
8 Correct 43 ms 41548 KB Output is correct
9 Correct 42 ms 41544 KB Output is correct
10 Correct 43 ms 41544 KB Output is correct
11 Correct 41 ms 41540 KB Output is correct
12 Correct 43 ms 41548 KB Output is correct
13 Correct 43 ms 41544 KB Output is correct
14 Correct 42 ms 41544 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 380 KB Output is correct
6 Correct 5 ms 352 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 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 6 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 -