oj.uz

Submission #623633

# Submission time Handle Problem Language Result Execution time Memory
623633 2022-08-06T07:25:26 Z Arnch Lamps (JOI19_lamps) C++17
0 / 100
 1000 ms 16396 KB 
// 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];

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];
		}
	}

	cout<<cnt[0][n - 1][1];
	return 0;

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

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

	cout<<dp[n - 1];

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Execution timed out 1092 ms 16396 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -