oj.uz

Submission #235730

# Submission time Handle Problem Language Result Execution time Memory
235730 2020-05-29T14:21:40 Z Charis02 Lamps (JOI19_lamps) C++14
0 / 100
 23 ms 16340 KB 
#include<iostream>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<queue>
#include<string.h>
#include<unordered_map>
#include<set>
#include<algorithm>
#define ll int
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define mid (low+high)/2
#define rep(i,a,b) for(int i = a;i < b;i++)
#define N 300004
#define INF 1000004

using namespace std;

ll n;
string s,t;
int dp[N][4];
/* 0: den ekana operation sto i, 1: kame to i set se 1, 2: kame to i set se 0,
3:kame to i toggle, 4: kame to i 1 kai meta toggle, 5: kame to i 0 kai meta toggle
*/
void solve()
{
    if(s[0]==t[0])
    {
        dp[0][0] = 0;
        dp[0][3] = INF;
    }
    else
    {
        dp[0][0] = INF;
        dp[0][3] = 1;
    }


    if(t[0] == '0')
    {
        dp[0][2] = 1;
        dp[0][1] = INF;

        dp[0][4] = 2;
        dp[0][5] = INF;
    }
    else
    {
        dp[0][1] = 1;
        dp[0][2] = INF;

        dp[0][4] = INF;
        dp[0][5] = 2;
    }

    rep(i,1,n)
    {
        if(s[i] == t[i])
        {
            dp[i][0] = min(dp[i-1][0],dp[i-1][1]);
            dp[i][0] = min(dp[i][0],dp[i-1][2]);
            dp[i][0] = min(dp[i][0],dp[i-1][3]);
            dp[i][0] = min(dp[i][0],dp[i-1][4]);
            dp[i][0] = min(dp[i][0],dp[i-1][5]);

            dp[i][3] = INF;
        }
        else
        {
            dp[i][0] = INF;

            dp[i][3] = min(dp[i-1][0]+1,dp[i-1][1]+1);
            dp[i][3] = min(dp[i][3],dp[i-1][2]+1);
            dp[i][3] = min(dp[i][3],dp[i-1][3]);
            dp[i][3] = min(dp[i][3],dp[i-1][4]);
            dp[i][3] = min(dp[i][3],dp[i-1][5]);
        }

        if(t[i] == '1')
        {
            dp[i][2] = INF;

            dp[i][1] = min(dp[i-1][0]+1,dp[i-1][1]);
            dp[i][1] = min(dp[i][1],dp[i-1][2]+1);
            dp[i][1] = min(dp[i][1],dp[i-1][3]+1);
            dp[i][1] = min(dp[i][1],dp[i-1][4]);

            dp[i][4] = INF;

            dp[i][5] = min(dp[i-1][0]+2,dp[i-1][1]+2);
            dp[i][5] = min(dp[i][5],dp[i-1][2]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][3]+1);
            dp[i][5] = min(dp[i][5],dp[i-1][4]+1);
        }
        else
        {
            dp[i][1] = INF;

            dp[i][2] = min(dp[i-1][0]+1,dp[i-1][2]);
            dp[i][2] = min(dp[i][2],dp[i-1][1]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][3]+1);
            dp[i][2] = min(dp[i][2],dp[i-1][5]);

            dp[i][5] = INF;

            dp[i][4] = min(dp[i-1][0]+2,dp[i-1][2]+2);
            dp[i][4] = min(dp[i][4],dp[i-1][1]+1);
            dp[i][4] = min(dp[i][4],dp[i-1][3]+1);
            dp[i][4] = min(dp[i][4],dp[i-1][5]+1);
        }
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    cin >> s;
    cin >> t;

    solve();
    cout << min({dp[n-1][0],dp[n-1][1],dp[n-1][2],dp[n-1][3],dp[n-1][4],dp[n-1][5]});

    return 0;
}

Compilation message

lamp.cpp: In function 'void solve()':
lamp.cpp:45:16: warning: array subscript is above array bounds [-Warray-bounds]
         dp[0][4] = 2;
         ~~~~~~~^
lamp.cpp:46:16: warning: array subscript is above array bounds [-Warray-bounds]
         dp[0][5] = INF;
         ~~~~~~~^
lamp.cpp:53:16: warning: array subscript is above array bounds [-Warray-bounds]
         dp[0][4] = INF;
         ~~~~~~~^
lamp.cpp:54:16: warning: array subscript is above array bounds [-Warray-bounds]
         dp[0][5] = 2;
         ~~~~~~~^
lamp.cpp:64:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][0] = min(dp[i][0],dp[i-1][4]);
                                     ~~~~~~~~~^
lamp.cpp:65:47: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][0] = min(dp[i][0],dp[i-1][5]);
                                               ^
lamp.cpp:65:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][0] = min(dp[i][0],dp[i-1][5]);
                                     ~~~~~~~~~^
lamp.cpp:76:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][3] = min(dp[i][3],dp[i-1][4]);
                                     ~~~~~~~~~^
lamp.cpp:77:47: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][3] = min(dp[i][3],dp[i-1][5]);
                                               ^
lamp.cpp:77:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][3] = min(dp[i][3],dp[i-1][5]);
                                     ~~~~~~~~~^
lamp.cpp:87:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][1] = min(dp[i][1],dp[i-1][4]);
                                     ~~~~~~~~~^
lamp.cpp:89:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][4] = INF;
             ~~~~~~~^
lamp.cpp:91:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = min(dp[i-1][0]+2,dp[i-1][1]+2);
             ~~~~~~~^
lamp.cpp:92:49: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = min(dp[i][5],dp[i-1][2]+1);
                                                 ^
lamp.cpp:92:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = min(dp[i][5],dp[i-1][2]+1);
             ~~~~~~~^
lamp.cpp:93:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = min(dp[i][5],dp[i-1][3]+1);
             ~~~~~~~^
lamp.cpp:94:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = min(dp[i][5],dp[i-1][4]+1);
                                     ~~~~~~~~~^
lamp.cpp:94:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = min(dp[i][5],dp[i-1][4]+1);
             ~~~~~~~^
lamp.cpp:103:47: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][2] = min(dp[i][2],dp[i-1][5]);
                                               ^
lamp.cpp:103:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][2] = min(dp[i][2],dp[i-1][5]);
                                     ~~~~~~~~~^
lamp.cpp:105:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][5] = INF;
             ~~~~~~~^
lamp.cpp:107:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][4] = min(dp[i-1][0]+2,dp[i-1][2]+2);
             ~~~~~~~^
lamp.cpp:108:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][4] = min(dp[i][4],dp[i-1][1]+1);
             ~~~~~~~^
lamp.cpp:109:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][4] = min(dp[i][4],dp[i-1][3]+1);
             ~~~~~~~^
lamp.cpp:110:46: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][4] = min(dp[i][4],dp[i-1][5]+1);
                                     ~~~~~~~~~^
lamp.cpp:110:20: warning: array subscript is above array bounds [-Warray-bounds]
             dp[i][4] = min(dp[i][4],dp[i-1][5]+1);
             ~~~~~~~^
lamp.cpp: In function 'int main()':
lamp.cpp:127:71: warning: array subscript is above array bounds [-Warray-bounds]
     cout << min({dp[n-1][0],dp[n-1][1],dp[n-1][2],dp[n-1][3],dp[n-1][4],dp[n-1][5]});
                                                              ~~~~~~~~~^
lamp.cpp:127:82: warning: array subscript is above array bounds [-Warray-bounds]
     cout << min({dp[n-1][0],dp[n-1][1],dp[n-1][2],dp[n-1][3],dp[n-1][4],dp[n-1][5]});
                                                                         ~~~~~~~~~^

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 304 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 304 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Runtime error 23 ms 16340 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 304 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Incorrect 5 ms 384 KB Output isn't correct
13 Halted 0 ms 0 KB -