oj.uz

답안 #206600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
206600 2020-03-04T07:42:32 Z egekabas Lamps (JOI19_lamps) C++14
4 / 100
 43 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+dp[i-1][1]);
        }
        else{
            dp[i][0] = min(dp[i][0], 1+dp[i-1][0]);
            dp[i][1] = min(dp[i][1], dp[i-1][1]);
        }
        dp[i][0] = min(dp[i][0], dp[same[i]-1][0]+1);
        dp[i][1] = min(dp[i][1], dp[same[i]-1][0]+1);
        
        dp[i][1] = min(dp[i][1], dp[i][0]);
        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

# 결과 실행 시간 메모리 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 4 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 Incorrect 5 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 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 4 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 Incorrect 5 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 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 4 ms 376 KB Output is correct
7 Correct 42 ms 41544 KB Output is correct
8 Correct 42 ms 41544 KB Output is correct
9 Correct 42 ms 41540 KB Output is correct
10 Correct 42 ms 41540 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 41548 KB Output is correct
14 Correct 43 ms 41544 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 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 4 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 Incorrect 5 ms 376 KB Output isn't correct
14 Halted 0 ms 0 KB -