제출 #376190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
376190		Kevin_Zhang_TW	Lamps (JOI19_lamps)	C++17	100 / 100	43 ms	27904 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 1000010, inf = 1e9;

int n;
char a[MAX_N], b[MAX_N];
int va[MAX_N], vb[MAX_N], pfa[MAX_N], pfb[MAX_N], dp[MAX_N], dif[MAX_N];

int bst[2], good;

int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> a+1 >> b+1;
	for (int i = 1;i <= n;++i) a[i] -= '0', b[i] -= '0';
	++n;
	for (int i = n;i >= 1;--i) {
		va[i] = a[i] ^ a[i-1];
		vb[i] = b[i] ^ b[i-1];
	}

	for (int i = 1;i <= n;++i) {
		pfa[i] = pfa[i-1] + va[i];
		pfb[i] = pfb[i-1] + vb[i];
		dif[i] = dif[i-1] + (va[i] != vb[i]);
	}

	if (accumulate(va, va+n+1, 0) == 0)
		return cout << accumulate(vb, vb + n + 1, 0) / 2 << '\n', 0;

	bst[0] = bst[1] = good = inf;

	for (int i = 0;i <= n;++i) {

		if (i == 0) {
			chmin(good, dp[i] - dif[i]);

			chmin(bst[ a[i+1] ],
					dp[i] + 2 + (va[i+1]==vb[i+1]) - pfb[i+1]);
			continue;
		}

		dp[i] = dif[i] + 1;

		chmin(dp[i], (va[i]==vb[i]) + pfb[i-1] 
				+ bst[ a[i-1] ]);

//		for (int j = 0;j < i;++j) {
//			if ( a[i-1] == a[j+1] ) {
//				// dp[j] + 2 + (va[j+1] == vb[j+1])  - pfb[j+1] + (va[i]==vb[i]) + pfb[i-1]
//				chmin(dp[i], 
//				 dp[j] + 2 + (va[j+1] == vb[j+1])  - pfb[j+1] + 
//				 (va[i]==vb[i]) + pfb[i-1]);
////				chmin(dp[i], dp[j] + 2 +
////						(va[i]==vb[i]) + (va[j+1]==vb[j+1]) + (pfb[i-1] - pfb[j+1]));
//			}
//		}

		chmin(dp[i], dif[i] + good);

		chmin(good, dp[i] - dif[i]);

		chmin(bst[ a[i+1] ],
				dp[i] + 2 + (va[i+1]==vb[i+1]) - pfb[i+1]);

	}

	cout << dp[n] / 2 << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp: In function 'int32_t main()':
lamp.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  cin >> n >> a+1 >> b+1;
      |              ~^~
lamp.cpp:27:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  cin >> n >> a+1 >> b+1;
      |                     ~^~
lamp.cpp:51:20: warning: array subscript has type 'char' [-Wchar-subscripts]
   51 |    chmin(bst[ a[i+1] ],
      |               ~~~~~^
lamp.cpp:59:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   59 |     + bst[ a[i-1] ]);
      |            ~~~~~^
lamp.cpp:76:19: warning: array subscript has type 'char' [-Wchar-subscripts]
   76 |   chmin(bst[ a[i+1] ],
      |              ~~~~~^

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