Submission #371200

#	Time	Username	Problem	Language	Result	Execution time	Memory
371200		azberjibiou	Lamps (JOI19_lamps)	C++17	100 / 100	103 ms	43520 KiB

lamp

#include <bits/stdc++.h>
#define fir first
#define sec second
#define ll long long
#define pll pair<ll, ll>
using namespace std;
const int mxN=1000100;
const int INF=10000001;
int N;
char A[mxN], B[mxN];
int state[mxN][5], dp[mxN][5];
int adj[5][5]={{0, 1, 1, 2, 2}, {0, 0, 1, 1, 2}, {0, 1, 0, 2, 1}, {0, 0, 1, 0, 4}, {0, 1, 0, 4, 0}};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    cin >> A+1;
    cin >> B+1;
    for(int i=1;i<=N;i++)
    {
        if(B[i]=='0')   state[i][2]=state[i][3]=1;
        else    state[i][1]=state[i][4]=1;
        if(A[i]!=B[i])   state[i][0]=1;
    }
    dp[0][1]=dp[0][2]=dp[0][3]=dp[0][4]=INF;
    for(int i=1;i<=N;i++)
    {
        for(int j=0;j<5;j++)    dp[i][j]=INF;
        for(int j=0;j<5;j++)
        {
            for(int k=0;k<5;k++)
            {
                int tmp=dp[i-1][k]+adj[k][j];
                if(state[i-1][k]==0 && state[i][j]==1)  tmp++;
                dp[i][j]=min(dp[i][j], tmp);
            }
        }
    }
    //for(int i=1;i<=N;i++)   for(int j=0;j<5;j++)    printf("dp[%d][%d]=%d\n", i, j, dp[i][j]);
    int ans=INF;
    for(int i=0;i<5;i++)
    {
        ans=min(ans, dp[N][i]);
    }
    cout << ans;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:18:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |     cin >> A+1;
      |            ~^~
lamp.cpp:19:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |     cin >> B+1;
      |            ~^~

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