Submission #122590

#	Time	Username	Problem	Language	Result	Execution time	Memory
122590		MvC	Lamps (JOI19_lamps)	C++11	100 / 100	196 ms	27900 KiB

lamp

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
//#include "rail.h"
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=1e6+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,t,x,y,rs=1e9,f[nmax][3][2],cs;
char c,a[nmax],b[nmax];
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>(a+1)>>(b+1);
	for(i=0;i<=n;i++)for(j=0;j<3;j++)for(t=0;t<2;t++)f[i][j][t]=1e9;
	f[0][0][0]=0;
	for(i=1;i<=n;i++)
	{
		for(j=0;j<3;j++)
		{
			for(t=0;t<2;t++)
			{
				for(x=0;x<3;x++)
				{
					for(y=0;y<2;y++)
					{
						c=a[i];
						cs=0;
						if(x==1)c='0';
						else if(x==2)c='1';
						if(y)c='0'+'1'-c;
						if(x!=j && x)cs++;
						if(y!=t && y)cs++;
						if(c==b[i])f[i][x][y]=min(f[i][x][y],f[i-1][j][t]+cs);
					}
				}
			}
		}
	}
	for(j=0;j<3;j++)for(t=0;t<2;t++)rs=min(rs,f[n][j][t]);
	cout<<rs<<endl;
    return 0;
}

Compilation message (stderr)

lamp.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
lamp.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

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