Submission #489152

#	Time	Username	Problem	Language	Result	Execution time	Memory
489152		cheissmart	Rope (JOI17_rope)	C++14	45 / 100	2576 ms	976 KiB

rope

#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emaplce_back
#define MP make_pair
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;

const int INF = 1e9 + 7, N = 1e6 + 7;

int c[N], ans[N];

void cmin(int& a, int b) {
	a = min(a, b);
}

signed main()
{
	IO_OP;

	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++) {
		cin >> c[i];
		c[i]--;
	}
	auto go = [&] (int x, int y) {
		int clr[] = {x, y};
		auto cost = [&] (int i, int color) {
			return int(clr[color] != c[i]);	
		};
		// dp[cut 01][last][parity]
		array<array<array<int, 2>, 2>, 2> dp;
		for(int i = 0; i < 2; i++)		
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					dp[i][j][k] = INF;
		dp[0][0][1] = cost(0, 0);
		dp[0][1][1] = cost(0, 1);
		for(int idx = 1; idx < n; idx++) {
			array<array<array<int, 2>, 2>, 2> ndp;
			for(int i = 0; i < 2; i++)		
				for(int j = 0; j < 2; j++)
					for(int k = 0; k < 2; k++)
						ndp[i][j][k] = INF;
			for(int i = 0; i < 2; i++)		
				for(int j = 0; j < 2; j++)
					for(int k = 0; k < 2; k++) {
						for(int l = 0; l < 2; l++) {
							if(j == l)
								cmin(ndp[i][l][k ^ 1], dp[i][j][k] + cost(idx, l));
							else {
								if(i && k) continue;
								cmin(ndp[1][l][1], dp[i][j][k] + cost(idx, l));
							}
						}
					}
			swap(dp, ndp);
		}
		int mn = INF;
		for(int i = 0; i < 2; i++)		
			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 2; k++)
					cmin(mn, dp[i][j][k]);
		return mn;
	};
	for(int i = 0; i < m; i++) 
		ans[i] = INF;
	for(int i = 0; i < m; i++) 
		for(int j = 0; j <= i; j++) {
			int tt = go(i, j);
			ans[i] = min(ans[i], tt);
			ans[j] = min(ans[j], tt);
		}
	for(int i = 0; i < m; i++)
		cout << ans[i] << '\n';	
		
}

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