Submission #173112

#	Time	Username	Problem	Language	Result	Execution time	Memory
173112		dennisstar	Lamps (JOI19_lamps)	C++11	4 / 100	199 ms	29816 KiB

lamp

#include <bits/stdc++.h>
#define fi first
#define se second
#define ryan bear
#define all(V) ((V).begin()), ((V).end())
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
typedef vector<int> vim;
typedef vector<ll> vlm;

int N;
int A[1000010], B[1000010];
int cl[1000010], ci[1000010], dif[1000010];
int Dp[1000010], mn[1000010];

int main() {
	scanf("%d", &N);
	for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
	for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
	for (int i=1, j; i<=N; i++) {
		cl[i]=cl[i-1]+1;
		for (j=i; j<=N; j++) {
			if (B[j]!=B[i]) break;
			cl[j]=cl[i];
			ci[j]=i;
		}
		i=j-1;
	}
	for (int i=1, j; i<=N; i++) {
		if (B[i]==A[i]) continue;
		for (j=i; j<=N; j++) {
			if (B[j]==A[j]) break;
			dif[j]=i;
		}
		i=j-1;
	}
	int st=1;
	for (st=1; st<=N; st++) if (A[st]!=B[st]) break;
	if (st>N) {
		puts("0"); return 0;
	}
	mn[st]=1-cl[st+1];
	Dp[st]=1;
	for (int i=st+1; i<=N; i++) {
		Dp[i]=Dp[i-1]; mn[i]=mn[i-1];
		if (A[i]==B[i]) continue;
		Dp[i]=Dp[dif[i]-1]+1;
		Dp[i]=min(Dp[i], mn[dif[i]-1]+cl[dif[i]-1]+1); mn[i]=min(mn[i], Dp[i]-cl[i+1]);
		Dp[i]=min(Dp[i], Dp[ci[i]-1]+1);
	}
	printf("%d\n", Dp[N]);
	return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
lamp.cpp:21:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%1d", &A[i]);
                           ~~~~~^~~~~~~~~~~~~~
lamp.cpp:22:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i=1; i<=N; i++) scanf("%1d", &B[i]);
                           ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 4 / 4
• Subtask 4: 0 / 49