Submission #197170

#	Time	Username	Problem	Language	Result	Execution time	Memory
197170		HellAngel	Lamps (JOI19_lamps)	C++14	100 / 100	106 ms	67276 KiB

lamp

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 1e6 + 6;

/// 0: on
/// 1: off
/// 2: tog
/// 3: on & tog
/// 4: off & tog
/// 5: tog & on
/// 6: tog & off
/// 7: do nothing

int dp[maxn][8];

void Minimize(int &a, const int &b)
{
    a = min(a, b);
}

void Update(int i, int j)
{
    if(j == 0) /// on
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0]);
        dp[i][j] = min(dp[i][j], dp[i - 1][1] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][2] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][3]);
        dp[i][j] = min(dp[i][j], dp[i - 1][4] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][5]);
        dp[i][j] = min(dp[i][j], dp[i - 1][6] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 1);
    }
    else if(j == 1) /// off
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][1]);
        dp[i][j] = min(dp[i][j], dp[i - 1][2] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][3] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][4]);
        dp[i][j] = min(dp[i][j], dp[i - 1][5] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][6]);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 1);
    }
    else if(j == 2) /// tog
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][1] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][2]);
        dp[i][j] = min(dp[i][j], dp[i - 1][3]);
        dp[i][j] = min(dp[i][j], dp[i - 1][4]);
        dp[i][j] = min(dp[i][j], dp[i - 1][5]);
        dp[i][j] = min(dp[i][j], dp[i - 1][6]);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 1);
    }
    else if(j == 3) /// on & tog
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][1] + 2);
        dp[i][j] = min(dp[i][j], dp[i - 1][2] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][3]);
        dp[i][j] = min(dp[i][j], dp[i - 1][4] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][5] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][6] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 2);
    }
    else if(j == 4) /// off & tog
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0] + 2);
        dp[i][j] = min(dp[i][j], dp[i - 1][1] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][2] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][3] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][4]);
        dp[i][j] = min(dp[i][j], dp[i - 1][5] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][6] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 2);
    }
    else if(j == 5) /// tog & on
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][1] + 2);
        dp[i][j] = min(dp[i][j], dp[i - 1][2] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][3] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][4] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][5]);
        dp[i][j] = min(dp[i][j], dp[i - 1][6] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 2);
    }
    else if(j == 6) /// tog & off
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0] + 2);
        dp[i][j] = min(dp[i][j], dp[i - 1][1] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][2] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][3] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][4] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][5] + 1);
        dp[i][j] = min(dp[i][j], dp[i - 1][6]);
        dp[i][j] = min(dp[i][j], dp[i - 1][7] + 2);
    }
    else if(j == 7)
    {
        dp[i][j] = min(dp[i][j], dp[i - 1][0]);
        dp[i][j] = min(dp[i][j], dp[i - 1][1]);
        dp[i][j] = min(dp[i][j], dp[i - 1][2]);
        dp[i][j] = min(dp[i][j], dp[i - 1][3]);
        dp[i][j] = min(dp[i][j], dp[i - 1][4]);
        dp[i][j] = min(dp[i][j], dp[i - 1][5]);
        dp[i][j] = min(dp[i][j], dp[i - 1][6]);
        dp[i][j] = min(dp[i][j], dp[i - 1][7]);
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    string s, t;
    int n;
    cin >> n;
    cin >> s >> t;
    fill_n(&dp[0][0], maxn*8, 1e9);
    if(s[0] == '0' && t[0] == '1')
    {
        dp[0][0] = dp[0][2] = 1;
        dp[0][4] = dp[0][5] = 2;
    }
    if(s[0] == '0' && t[0] == '0')
    {
        dp[0][1] = 1;
        dp[0][3] = dp[0][6] = 2;
        dp[0][7] = 0;
    }
    if(s[0] == '1' && t[0] == '0')
    {
        dp[0][1] = dp[0][2] = 1;
        dp[0][3] = dp[0][6] = 2;
    }
    if(s[0] == '1' && t[0] == '1')
    {
        dp[0][0] = 1;
        dp[0][4] = dp[0][5] = 2;
        dp[0][7] = 0;
    }
    for(int i = 1; i < s.length(); i++)
    {
        if(s[i] == '0' && t[i] == '1')
        {
            Update(i, 0);
            Update(i, 2);
            Update(i, 4);
            Update(i, 5);
        }
        if(s[i] == '0' && t[i] == '0')
        {
            Update(i, 1);
            Update(i, 3);
            Update(i, 6);
            Update(i, 7);
        }
        if(s[i] == '1' && t[i] == '1')
        {
            Update(i, 0);
            Update(i, 4);
            Update(i, 5);
            Update(i, 7);
        }
        if(s[i] == '1' && t[i] == '0')
        {
            Update(i, 1);
            Update(i, 2);
            Update(i, 3);
            Update(i, 6);
        }
    }
    int ans = 1e9;
    for(int i = 0; i <= 7; i++)
    {
        ans = min(ans, dp[s.length() - 1][i]);
    }
    cout << ans;
}

Compilation message (stderr)

lamp.cpp: In function 'int32_t main()':
lamp.cpp:148:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < s.length(); i++)
                    ~~^~~~~~~~~~~~
lamp.cpp:120:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:120:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

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