Submission #623641

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
623641	2022-08-06T07:52:41 Z	Arnch	Lamps (JOI19_lamps)	C++17	0 / 100	5 ms	4644 KB

lamp

// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 2e3 + 10;

int cnt[N][N][2];
int dp[N][2];

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	int n; cin >>n;
	string A, B; cin >>A >>B;

	assert(n <= 2000);

	for(int i = 0; i < n; i++) {
		for(int j = i; j < n; j++) {
			cnt[i][j][0] = (B[j] == '0');	
			cnt[i][j][1] = (B[j] == '1');
			
			if(i == j) continue;
			
			cnt[i][j][0] -= (B[j - 1] == '0' && B[j] == '0');	
			cnt[i][j][1] -= (B[j - 1] == '1' && B[j] == '1');

			cnt[i][j][0] += cnt[i][j - 1][0];
			cnt[i][j][1] += cnt[i][j - 1][1];
		}
	}

	memset(dp, 63, sizeof(dp));

	int pos = 0;
	if(A[0] != B[0]) pos = -1, dp[0][0] = dp[0][1] = 1;
	else dp[0][1] = 0;

	for(int i = 1; i < n; i++) {
		if(A[i] == B[i]) {
			dp[i][1] = dp[i - 1][1];
			pos = i;
			continue;
		}
		if(pos == -1) {
			dp[i][0] = dp[i][1] = 1;
			continue;
		}
		dp[i][0] = dp[pos][1] + 1;
		dp[i][1] = dp[i][0];
		for(int j = i; j >= 0; j--) {
			int val = 0;
			if(j == 0) {
				val += 1 + min(cnt[j][i][0], cnt[j][i][1]);
				dp[i][1] = min(dp[i][1], val);
				continue;
			}
			val = dp[j - 1][1];
			val += 1 + min(cnt[j][i][0], cnt[j][i][1]);
			dp[i][1] = min(dp[i][1], val);
			if(B[j] == '1') {
				if(A[j - 1] != B[j - 1]) {
					dp[i][1] = min(dp[i][1], dp[j - 1][0] + cnt[j][i][0]);
				}
			}
			else {
				if(A[j - 1] != B[j - 1]) {
					dp[i][1] = min(dp[i][1], dp[j - 1][0] + cnt[j][i][1]);
				}
			}
		}
	//	wtf(i), wtf(pos), wtf(dp[i]), wtf(cnt[0][i][1]), wtf(cnt[0][i][0]);
	}

	cout<<dp[n - 1][1];

    return 0;
}

Subtask #1

0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Incorrect	0 ms	340 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #2

0 / 41.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Incorrect	0 ms	340 KB	Output isn't correct
24	Halted	0 ms	0 KB	-

Subtask #3

0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Runtime error	5 ms	4644 KB	Execution killed with signal 6
8	Halted	0 ms	0 KB	-

Subtask #4

0 / 49.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	0 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	0 ms	340 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	1 ms	380 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	1 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	0 ms	332 KB	Output is correct
21	Correct	1 ms	332 KB	Output is correct
22	Correct	0 ms	340 KB	Output is correct
23	Incorrect	0 ms	340 KB	Output isn't correct
24	Halted	0 ms	0 KB	-