Submission #134474

#	Time	Username	Problem	Language	Result	Execution time	Memory
134474		doowey	Lamps (JOI19_lamps)	C++14	100 / 100	106 ms	27980 KiB

lamp

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll, ll> pii;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
const int N = (int)1e6 + 9;
int dp[N][3][2];

int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 0 ; i < N ;i  ++ ){
        for(int j = 0 ; j < 3 ; j ++ ) 
            for(int z = 0; z < 2 ;z ++ )
                dp[i][j][z] = 12124141;
    }   
    string a, b;
    cin >> a >> b;
    int from, to;
    int nw;
    int sum;
    dp[0][0][0] = 0;
    for(int i = 1 ; i <= n; i ++ ){
        from = a[i-1] - '0';
        to = b[i-1] - '0';
        for(int j = 0 ; j < 3; j ++ ){
            for(int z = 0 ;z < 2; z ++ ){
                nw = from;
                if(j) nw = j - 1;
                if(z) nw ^= 1;
                if(nw == to){
                    for(int v = 0; v < 3 ;v ++ ){
                        for(int q = 0 ;q < 2; q ++ ){
                            sum = dp[i-1][v][q];
                            if(j > 0 && j != v) sum ++ ;
                            if(z > 0 && z != q) sum ++ ;
                            dp[i][j][z] = min(dp[i][j][z], sum);
                        }
                    }
                }
            }
        }
    }
    int res = 124214124;
    for(int i = 0 ; i < 3; i ++ )
        for(int j = 0 ; j < 2; j ++ ){
            res = min(res, dp[n][i][j]);
        }
    cout << res;
    return 0;
}

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