Submission #20925

#	Time	Username	Problem	Language	Result	Execution time	Memory
20925		gs14004	Rope (JOI17_rope)	C++11	45 / 100	29 ms	21552 KiB

rope

#include <bits/stdc++.h>
typedef long long lint;
typedef long double llf;
using namespace std;
typedef pair<int, int> pi;

int n, m, a[1000005];
int ans[1000005];
int dp[1000005][3];

int solve(int x, int y){
	for(int i=1; i<=n; i++){
		dp[i][0] = dp[i-1][1] + (a[i] != x);
		dp[i][1] = min(dp[i-1][0] + (a[i] != x), dp[i-1][2] + (a[i] != y));
		dp[i][2] = dp[i-1][1] + (a[i] != y);
	}
	return min({dp[n][0], dp[n][1], dp[n][2]});
}

int main(){
	scanf("%d %d",&n,&m);
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
	}
	if(m > 10) return 0;
	memset(ans, 0x3f, sizeof(ans));
	for(int i=1; i<=m; i++){
		for(int j=1; j<=i; j++){
			int x = solve(i, j);
			ans[i] = min(ans[i], x);
			ans[j] = min(ans[j], x);
		}
	}
	for(int i=1; i<=m; i++) printf("%d\n", ans[i]);
}

Compilation message (stderr)

rope.cpp: In function 'int main()':
rope.cpp:21:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
                      ^
rope.cpp:23:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

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