Submission #132553

#	Time	Username	Problem	Language	Result	Execution time	Memory
132553		MrTEK	Lamps (JOI19_lamps)	C++14	0 / 100	10 ms	4472 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair <int,int> ii;

const int N = 2e3 + 5;
const int inf = 2e9;
const int SQ = 300;

int n,d[2][N][N],dp[N][2];
char a[2][N],b[N];

int f(int cur,int w) {
	if (cur == n + 1)
		return 0;
	int &res = dp[cur][w];
	if (res != -1)
		return res;
	res = 1e9;
	for (int i = cur ; i <= n ; i++)
		res = min(res,d[w][cur][i] +  f(i + 1,!w));
	return res += (w == 1);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL) ; cout.tie(NULL);
	cin >> n >> (a[0] + 1) >> (b + 1);
	for (int i = 1 ; i <= n ; i++)
		a[1][i] = !(a[0][i] - '0') + '0';
	for (int w = 0 ; w < 2 ; w++) {
		for (int i = n ; i >= 1 ; i--) {
			int j = i;
			while(j + 1 <= n && b[j + 1] == b[i])
				j++;
			int flag = 0;
			for (int k = i ; k <= j ; k++) {
				if (a[w][k] != b[k])
					flag = 1;
				d[w][i][k] = flag;
			}
			for (int k = j + 1 ; k <= n ; k++)
				d[w][i][k] = d[w][i][j] + d[w][j + 1][k];
		}
	}
	memset(dp,-1,sizeof dp);
	cout << min(f(1,0),f(1,1)) << endl;
}

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