Submission #256338

#	Time	Username	Problem	Language	Result	Execution time	Memory
256338		lyc	Lamps (JOI19_lamps)	C++14	4 / 100	30 ms	27860 KiB

lamp

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)

#define chmin(x,y) x = min(x,y)

const int mxN = 1e6+5;

int N;
string A, B;

int dp[mxN][6];

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> N >> A >> B;
	
	FOR(x,0,5) dp[N][x] = 0;
	RFOR(i,N-1,0){
		if (A[i] == B[i]) FOR(x,0,5) dp[i][x] = dp[i+1][0];
		else FOR(x,0,5) dp[i][x] = dp[i+1][1] + (x!=1);
		if (B[i] == '0') {
			chmin(dp[i][0], dp[i+1][2]+1);
			chmin(dp[i][1], dp[i+1][2]+1);
			chmin(dp[i][2], dp[i+1][2]);
			chmin(dp[i][3], dp[i+1][2]);
			chmin(dp[i][4], dp[i+1][4]);
			chmin(dp[i][5], dp[i+1][4]+1);
		} else {
			chmin(dp[i][0], dp[i+1][5]+1);
			chmin(dp[i][1], dp[i+1][5]+1);
			chmin(dp[i][2], dp[i+1][3]+1);
			chmin(dp[i][3], dp[i+1][3]);
			chmin(dp[i][4], dp[i+1][5]);
			chmin(dp[i][5], dp[i+1][5]);
		}
		
		//~ cout << i << " :: ";
		//~ FOR(x,0,3) cout << dp[i][x] << ' ';
		//~ cout << endl;
	}
	cout << dp[0][0] << '\n';
}

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