Submission #1177208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177208		8pete8	Lamps (JOI19_lamps)	C++20	100 / 100	81 ms	80792 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
#define sz(x) (int)((x).size())
#define int long long
using namespace std;
const int mod=1e9+7,mxn=1e6,inf=1e18,minf=-1e18,lg=30,Mxn=1e6;
//#undef int
int n,k,m,d,q;
void setIO(string name){
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
int dp[mxn+10][5][2];
//none, 1, 01, 0 , 10
//0 1 2 3 4
int wat[5];
vector<pii>adj[5];
int32_t main(){
	fastio
	int n;cin>>n;
	string a;cin>>a;
	string b;cin>>b;
	wat[1]=wat[2]=1;
	for(int i=0;i<5;i++)adj[0].pb({i,0});

	for(int i=0;i<4;i++)if(i!=1)adj[1].pb({i,1});
	adj[1].pb({4,0});

	for(int i=0;i<5;i++)if(i!=3&&i!=2)adj[2].pb({i,2});
	adj[2].pb({3,1});
	
	for(int i=0;i<5;i++)if(i!=2&&i!=3)adj[3].pb({i,1});
	adj[3].pb({2,0});

	for(int i=0;i<5;i++)if(i!=1&&i!=4)adj[4].pb({i,2});
	adj[4].pb({1,1});

	for(int i=1;i<5;i++)adj[i].pb({i,0});
	for(int i=0;i<=n;i++)for(int j=0;j<5;j++){
		for(int g=0;g<2;g++)dp[i][j][g]=inf;
	}
	dp[0][0][0]=0;
	for(int i=1;i<=n;i++){
		int x=b[i-1]-'0';
		wat[0]=a[i-1]-'0';
		for(int j=0;j<5;j++)for(int k=0;k<2;k++){
			if((wat[j]^k)==x){
				for(auto g:adj[j]){
					for(int p=0;p<2;p++){
						dp[i][j][k]=min(dp[i][j][k],dp[i-1][g.f][p]+g.s+(p==0&&k==1));
					}
				}
			}
		}
	}
	
	int ans=inf;
	for(int i=0;i<5;i++)for(int j=0;j<2;j++)ans=min(ans,dp[n][i][j]);
	cout<<ans;
}
/*
interval dp?
observations:
considering only using 2 first operations
we can create any kind of pattern while having at most 2 operation performed on each cell

How about the third operation?
We can always assume that the third operation can always be done after 1,2 operation
why?

if the third operation completely covers 1,2 operation we can easily see that its just like switching 1,2 operation
if the third operation is completely covered by 1,2 operation it doesnt have any effect
we can also further prove for cases like intersecting between layers

these should be enough to conclude that there has to be an order of operation where 3rd operation is applied after 1,2 operation and still gives the min cost.
*/

Compilation message (stderr)

lamp.cpp:16:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   16 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
lamp.cpp:23:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   23 | void setIO(string name){
      |                       ^
lamp.cpp:33:14: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   33 | int32_t main(){
      |              ^
lamp.cpp: In function 'void setIO(std::string)':
lamp.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen((name+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen((name+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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