oj.uz

Submission #173112

# Submission time Handle Problem Language Result Execution time Memory
173112 2020-01-03T11:38:17 Z dennisstar Lamps (JOI19_lamps) C++11
4 / 100
 199 ms 29816 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Incorrect 2 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Incorrect 2 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 180 ms 18088 KB Output is correct
8 Correct 196 ms 29684 KB Output is correct
9 Correct 196 ms 29688 KB Output is correct
10 Correct 196 ms 29816 KB Output is correct
11 Correct 199 ms 29692 KB Output is correct
12 Correct 198 ms 29788 KB Output is correct
13 Correct 191 ms 28284 KB Output is correct
14 Correct 192 ms 29704 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Incorrect 2 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -