Submission #1311976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311976		nanaseyuzuki	Lamps (JOI19_lamps)	C++20	47 / 100	17 ms	15984 KiB

lamp

#include <bits/stdc++.h>
// Kazusa_Megumi
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, dp[mn][6], val[6][6];
string a, b;
// dp[i][0] : keep
// dp[i][1] : toggle
// dp[i][2] : set 0
// dp[i][3] : set 1
// dp[i][4] : set 0 + toggle
// dp[i][5] : set 1 + toggle

void solve() {
    cin >> n >> a >> b;
    fill(&dp[0][0], &dp[0][0] + mn * 6, inf);
    a = "#" + a, b = "#" + b;
    for(int i = 0; i < 6; i++){
    	for(int j = 0; j < 6; j++){
    		if(j == 0 || i == j) val[i][j] = 0;
    		else if(j == 1) val[i][j] = (i >= 4 ? 0 : 1);
    		else if(j == 2) val[i][j] = (i == 4 ? 0 : 1);
    		else if(j == 3) val[i][j] = (i == 5 ? 0 : 1);
    		else if(j == 4) val[i][j] = ((i == 1 || i == 2) ? 1 : 2);
    		else if(j == 5) val[i][j] = ((i == 1 || i == 3) ? 1 : 2);
    	}
    }

    dp[0][0] = 0;
    for(int i = 1; i <= n; i++){
    	int st = a[i] - '0';
		for(int nxt = 0; nxt < 6; nxt ++){
			int cur = st;
			if(nxt > 1) cur = (nxt <= 3 ? nxt - 2 : 1 - (nxt - 4));
			else if(nxt == 1) cur = 1 - cur; 

			if(cur != b[i] - '0') continue;
    		for(int pre = 0; pre < 6; pre ++){
    			dp[i][nxt] = min(dp[i][nxt], dp[i - 1][pre] + val[pre][nxt]);
    		}
    	}
    }

    int res = inf;
    for(int i = 0; i < 6; i++) res = min(res, dp[n][i]);
   	cout << res << '\n';
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("Kazuki.INP", "r")) {
        freopen("Kazuki.INP", "r", stdin);
        freopen("Kazuki.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

lamp.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   62 | main() {
      | ^~~~
lamp.cpp: In function 'int main()':
lamp.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen("Kazuki.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:67:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         freopen("Kazuki.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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