oj.uz

Submission #210244

# Submission time Handle Problem Language Result Execution time Memory
210244 2020-03-17T00:21:17 Z tri Lamps (JOI19_lamps) C++14
0 / 100
 137 ms 35612 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

const int MAXN = 1e6;
const int INF = 1e8;

int N;
string As, Bs;

int a[MAXN], b[MAXN];

int dp[MAXN][3][2];

int main() {
    cin >> N;
    cin >> As >> Bs;

    As = ' ' + As;
    Bs = ' ' + Bs;

    for (int i = 1; i <= N; i++) {
        a[i] = As[i] - '0';
        b[i] = Bs[i] - '0';
    }
    a[0] = b[0] = 0; // initialize to be the same so no toggle needed

    for (int i = 0; i < MAXN; i++) {
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 2; k++) {
                dp[i][j][k] = INF;
            }
        }
    }

    dp[0][0][0] = 0;

    for (int i = 0; i < N; i++) {
        // case 1: nothing
        int tog = a[i] ^b[i];
        int cCost = dp[i][0][0];

        if (cCost != INF) {
            // case 1a: continue nothing
            int nTog = a[i + 1] ^b[i + 1];
            int nCost = cCost + (tog ^ nTog);

            dp[i + 1][0][0] = min(dp[i + 1][0][0], nCost);

            // case 1b: add a set
            for (int nSet = 0; nSet < 2; nSet++) {
                int nTog = nSet ^b[i + 1];
                int nCost = cCost + 1 + (tog ^ nTog);

                dp[i + 1][1][nSet] = min(dp[i + 1][1][nSet], nCost);
            }
        }

        // case 2: 1 set
        for (int cSet = 0; cSet < 2; cSet++) {
            int tog = cSet ^b[i];
            int cCost = dp[i][1][cSet];
            if (cCost != INF) {
                // case 2a: continue/change cSet
                for (int nSet = 0; nSet < 2; nSet++) {
                    int nTog = nSet ^b[i + 1];
                    int nCost = cCost + (cSet ^ nSet) + (tog ^ nTog);
                    dp[i + 1][1][nSet] = min(dp[i + 1][1][nSet], nCost);
                }


                // case 2b: stop set
                int nTog = a[i + 1] ^b[i + 1];
                int nCost = cCost + (tog ^ nTog);
                dp[i + 1][0][0] = min(dp[i + 1][0][0], nCost);


                // case 2c: add second set that is opposite of cSet
                nTog = (cSet ^ 1) ^ b[i + 1];
                nCost = cCost + 1 + (tog ^ nTog);
                dp[i + 1][2][cSet] = min(dp[i + 1][2][cSet], nCost);
            }
        }

        // case 3: 2 sets, cSet is the the base set
        for (int cSet = 0; cSet < 2; cSet++) {
            int tog = cSet ^1 ^b[i];
            int cCost = dp[i][2][cSet];
            if (cCost != INF) {
                // case 2a: continue cSet
                int nTog = cSet ^1 ^b[i + 1];
                int nCost = cCost + (tog ^ nTog);
                dp[i + 1][2][cSet] = min(dp[i + 1][2][cSet], nCost);

                // case 2b: stop second set
                nTog = cSet ^ b[i + 1];
                nCost = cCost + (tog ^ nTog);
                dp[i + 1][1][cSet] = min(dp[i + 1][1][cSet], nCost);
            }
        }
    }

    int ans = INF;

    // case 1: no set
    ans = min(ans, dp[N][0][0]);

    // case 2: 1 set
    ans = min(ans, dp[N][1][0]);
    ans = min(ans, dp[N][1][1]);

    // case 2: 2 set
    ans = min(ans, dp[N][2][0]);
    ans = min(ans, dp[N][2][1]);

    cout << ans << endl;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 18 ms 23800 KB Output is correct
5 Correct 22 ms 23804 KB Output is correct
6 Correct 18 ms 23800 KB Output is correct
7 Correct 18 ms 23800 KB Output is correct
8 Correct 18 ms 23800 KB Output is correct
9 Correct 18 ms 23800 KB Output is correct
10 Correct 18 ms 23800 KB Output is correct
11 Correct 18 ms 23756 KB Output is correct
12 Correct 18 ms 23800 KB Output is correct
13 Incorrect 17 ms 23800 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 18 ms 23800 KB Output is correct
5 Correct 22 ms 23804 KB Output is correct
6 Correct 18 ms 23800 KB Output is correct
7 Correct 18 ms 23800 KB Output is correct
8 Correct 18 ms 23800 KB Output is correct
9 Correct 18 ms 23800 KB Output is correct
10 Correct 18 ms 23800 KB Output is correct
11 Correct 18 ms 23756 KB Output is correct
12 Correct 18 ms 23800 KB Output is correct
13 Incorrect 17 ms 23800 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23800 KB Output is correct
3 Correct 18 ms 23804 KB Output is correct
4 Correct 19 ms 23800 KB Output is correct
5 Correct 18 ms 23800 KB Output is correct
6 Correct 17 ms 23800 KB Output is correct
7 Correct 137 ms 35612 KB Output is correct
8 Incorrect 137 ms 35508 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23800 KB Output is correct
2 Correct 18 ms 23800 KB Output is correct
3 Correct 19 ms 23800 KB Output is correct
4 Correct 18 ms 23800 KB Output is correct
5 Correct 22 ms 23804 KB Output is correct
6 Correct 18 ms 23800 KB Output is correct
7 Correct 18 ms 23800 KB Output is correct
8 Correct 18 ms 23800 KB Output is correct
9 Correct 18 ms 23800 KB Output is correct
10 Correct 18 ms 23800 KB Output is correct
11 Correct 18 ms 23756 KB Output is correct
12 Correct 18 ms 23800 KB Output is correct
13 Incorrect 17 ms 23800 KB Output isn't correct
14 Halted 0 ms 0 KB -