Submission #127726

#	Time	Username	Problem	Language	Result	Execution time	Memory
127726		EntityIT	Rope (JOI17_rope)	C++14	45 / 100	2532 ms	1144 KiB

rope

#include<bits/stdc++.h>

using namespace std;

int n, m, mn[2][2][2];
vector<int> c, ans;

void update (int &_a, int _b) {
    if (_a == -1 || _a > _b) _a = _b;
}

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

    cin >> n >> m;
    c.assign(n + 5, 0);
    for (int i = 1; i <= n; ++i) cin >> c[i];
    ans.assign(m + 5, n + 5);

    int color[2];
    for (color[0] = 1; color[0] <= m; ++color[0]) {
        for (color[1] = 1; color[1] <= m; ++color[1]) {
            memset(mn, -1, sizeof mn);
            mn[1][1][0] = (c[1] != color[0]);
            mn[1][1][1] = (c[1] != color[1]);

            for (int iC = 2; iC <= n; ++iC) {
                int _mn[2][2][2]; memset(_mn, -1, sizeof _mn);

                for (int i = 0; i < 2; ++i) {
                    for (int j = 0; j < 2; ++j) {
                        for (int k = 0; k < 2; ++k) if (mn[i][j][k] != -1) {
                            update(_mn[i][j ^ 1][k], mn[i][j][k] + (c[iC] != color[k]) );
                            if (i || !j) update(_mn[0][1][k ^ 1], mn[i][j][k] + (c[iC] != color[k ^ 1]) );
                        }
                    }
                }

                for (int i = 0; i < 2; ++i) {
                    for (int j = 0; j < 2; ++j) {
                        for (int k = 0; k < 2; ++k) mn[i][j][k] = _mn[i][j][k];
                    }
                }
            }

            for (int i = 0; i < 2; ++i) {
                for (int j = 0; j < 2; ++j) {
                    for (int k = 0; k < 2; ++k) if (mn[i][j][k] != -1) {
                        if (!i || !k) update(ans[ color[0] ], mn[i][j][k]);
                        if (!i || k) update(ans[ color[1] ], mn[i][j][k]);
                    }
                }
            }
        }
    }

    for (int i = 1; i <= m; ++i) cout << ans[i] << '\n';

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 30 / 30
• Subtask 3: 0 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 20