Submission #488571

#	Time	Username	Problem	Language	Result	Execution time	Memory
488571		keta_tsimakuridze	Lamps (JOI19_lamps)	C++14	100 / 100	95 ms	33872 KiB

lamp

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
#define int long long
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7; // !
int t, n,dp[N][4];
string s1,s2;
int get(char c, int k) {
	if(c == '#') return '#';
	if(!k) return c;
	if(k == 2) return '1';
	return '0';
}
main() {
	cin >> n;
	cin >> s1 >> s2;
	int n = s1.size();
	s1 = '#' + s1, s2 = '#' + s2;
	dp[0][0] = 0;
	for(int k = 1; k < 3; k++) dp[0][k] = n;
	for(int i = 1; i <= n; i++) { 
		for(int k = 0; k < 3; k++) {dp[i][k] = n;
			for(int j = 0; j < 3; j++) {
			
				int plus = 0;
				if(k != j && k) plus += 1; 
				if(get(s1[i], k) != s2[i]) {
					if(get(s1[i - 1], j) == s2[i - 1]) plus++; 
				}
				
				dp[i][k] = min(dp[i][k], dp[i - 1][j] + plus);
			}
	//		cout << dp[i][k] <<" ";
		}
	//	 cout << endl;
	}
	cout << min(dp[n][0], min(dp[n][1], dp[n][2]));
}

Compilation message (stderr)

lamp.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~

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