oj.uz

Submission #235732

# Submission time Handle Problem Language Result Execution time Memory
235732 2020-05-29T14:22:11 Z Charis02 Lamps (JOI19_lamps) C++14
0 / 100
 27 ms 19028 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<unordered_map>
#include<set>
#include<algorithm>
#define ll int
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1000004

using namespace std;

ll n;
string s,t;
int dp[N][6];
/* 0: den ekana operation sto i, 1: kame to i set se 1, 2: kame to i set se 0,
3:kame to i toggle, 4: kame to i 1 kai meta toggle, 5: kame to i 0 kai meta toggle
*/
void solve()
{
    if(s[0]==t[0])
    {
        dp[0][0] = 0;
        dp[0][3] = INF;
    }
    else
    {
        dp[0][0] = INF;
        dp[0][3] = 1;
    }


    if(t[0] == '0')
    {
        dp[0][2] = 1;
        dp[0][1] = INF;

        dp[0][4] = 2;
        dp[0][5] = INF;
    }
    else
    {
        dp[0][1] = 1;
        dp[0][2] = INF;

        dp[0][4] = INF;
        dp[0][5] = 2;
    }

    rep(i,1,n)
    {
        if(s[i] == t[i])
        {
            dp[i][0] = min(dp[i-1][0],dp[i-1][1]);
            dp[i][0] = min(dp[i][0],dp[i-1][2]);
            dp[i][0] = min(dp[i][0],dp[i-1][3]);
            dp[i][0] = min(dp[i][0],dp[i-1][4]);
            dp[i][0] = min(dp[i][0],dp[i-1][5]);

            dp[i][3] = INF;
        }
        else
        {
            dp[i][0] = INF;

            dp[i][3] = min(dp[i-1][0]+1,dp[i-1][1]+1);
            dp[i][3] = min(dp[i][3],dp[i-1][2]+1);
            dp[i][3] = min(dp[i][3],dp[i-1][3]);
            dp[i][3] = min(dp[i][3],dp[i-1][4]);
            dp[i][3] = min(dp[i][3],dp[i-1][5]);
        }

        if(t[i] == '1')
        {
            dp[i][2] = INF;

            dp[i][1] = min(dp[i-1][0]+1,dp[i-1][1]);
            dp[i][1] = min(dp[i][1],dp[i-1][2]+1);
            dp[i][1] = min(dp[i][1],dp[i-1][3]+1);
            dp[i][1] = min(dp[i][1],dp[i-1][4]);

            dp[i][4] = INF;

            dp[i][5] = min(dp[i-1][0]+2,dp[i-1][1]+2);
            dp[i][5] = min(dp[i][5],dp[i-1][2]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][3]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][4]+1);
        }
        else
        {
            dp[i][1] = INF;

            dp[i][2] = min(dp[i-1][0]+1,dp[i-1][2]);
            dp[i][2] = min(dp[i][2],dp[i-1][1]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][3]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][5]);

            dp[i][5] = INF;

            dp[i][4] = min(dp[i-1][0]+2,dp[i-1][2]+2);
            dp[i][4] = min(dp[i][4],dp[i-1][1]+1);
            dp[i][4] = min(dp[i][4],dp[i-1][3]+1);
            dp[i][4] = min(dp[i][4],dp[i-1][5]+1);
        }
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    cin >> s;
    cin >> t;

    solve();
    cout << min({dp[n-1][0],dp[n-1][1],dp[n-1][2],dp[n-1][3],dp[n-1][4],dp[n-1][5]});

    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

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

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Runtime error 27 ms 19028 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

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