Submission #254613

#	Time	Username	Problem	Language	Result	Execution time	Memory
254613		pit4h	Rope (JOI17_rope)	C++14	45 / 100	2570 ms	1152 KiB

rope

#include<bits/stdc++.h>
using namespace std;

int solve(int c1, int c2, vector<int>& a, int m) {
	int n = a.size(); 
	vector<vector<int>> dp(3, vector<int>(3, n));
	dp[0][0] = 0;
	for(int i=0; i<n; ++i) {
		vector<vector<int>> ndp(3, vector<int>(3, n));
		ndp[2][0] = min(dp[2][0], dp[0][0]) + ((a[i]==c1)?0:1);
		ndp[2][1] = min(dp[2][2], dp[0][2]) + ((a[i]==c1)?0:1);
		ndp[2][2] = min(dp[2][1], dp[0][1]) + ((a[i]==c1)?0:1);

		ndp[0][2] = min(dp[0][2], dp[0][0]) + ((a[i]==c2)?0:1);
		ndp[1][2] = min(dp[2][2], dp[2][0]) + ((a[i]==c2)?0:1);
		ndp[2][2] = min(ndp[2][2], min(dp[1][2], dp[1][0]) + ((a[i]==c2)?0:1));
		
		//cerr<<"iter "<<i<<' '<<a[i]<<' '<<dp[2][1]+((a[i]==c1)?0:1)<<'\n';
		dp = ndp;
		/*for(int x=0; x<=2; ++x) {
			for(int y=0; y<=2; ++y) {
				cerr<<dp[x][y]<<' ';
			}
			cerr<<'\n';
		}
		cerr<<'\n';*/
	}
	int res = n;
	for(int i=0; i<=2; ++i) {
		for(int j=0; j<=2; ++j) {
			res = min(res, dp[i][j]);
		}
	}
	return res;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, m;
	cin>>n>>m;
	vector<int> a(n);
	for(int i=0; i<n; ++i) {
		cin>>a[i];	
	}
	for(int i=1; i<=m; ++i) {
		int ans = n;
		for(int j=1; j<=m; ++j) {
			ans = min(ans, solve(i, j, a, m));	
			//cerr<<"solve "<<i<<' '<<j<<": "<<solve(i, j, a, m)<<'\n';
		}
		cout<<ans<<'\n';
	}
}

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