oj.uz

답안 #917322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
917322 2024-01-27T19:36:56 Z amirhoseinfar1385 Lamps (JOI19_lamps) C++17
4 / 100
 35 ms 27816 KB 
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+10;
int dp[maxn][2][3],inf=maxn+10;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	string s,ss;
	cin>>n>>s>>ss;
	for(int i=0;i<2;i++){
		for(int j=0;j<3;j++){
			dp[0][i][j]=inf;
		}
	}
	dp[0][0][2]=0;
	for(int ind=1;ind<=n;ind++){
		for(int i=0;i<2;i++){
			for(int j=0;j<2;j++){
				dp[ind][i][j]=min(dp[ind-1][i^1][j]+(i==1),min(dp[ind-1][i^1][j^1]+(i==1),dp[ind-1][i^1][2]+(i==1))+1);
				dp[ind][i][j]=min(dp[ind-1][i][j],min(dp[ind-1][i][j^1],dp[ind-1][i][2])+1);	
			}
			dp[ind][i][2]=min(dp[ind-1][i][0],min(dp[ind-1][i][1],dp[ind-1][i][2]));
			dp[ind][i][2]=min(dp[ind][i][2],min(dp[ind-1][i^1][0],min(dp[ind-1][i^1][1],dp[ind-1][i^1][2]))+(i==1));
		}
		if(s[ind-1]==ss[ind-1]){
			dp[ind][0][(s[ind-1]-'0')^1]=inf;
			dp[ind][1][(s[ind-1]-'0')]=inf;
			dp[ind][1][2]=inf;
		}
		else{
			dp[ind][0][(s[ind-1]-'0')]=inf;
			dp[ind][0][2]=inf;
			dp[ind][1][(s[ind-1]-'0')^1]=inf;
		}
//		cout<<"injy: "<<ind<<"\n";
//		for(int i=0;i<2;i++){
//			for(int j=0;j<3;j++){
//				cout<<dp[ind][i][j]<<" ";
//			}
//			cout<<"\n";
//		}
//		cout<<"\n";
	}
	long long res=min(dp[n][0][0],min(dp[n][0][1],min(dp[n][0][2],min(dp[n][1][0],min(dp[n][1][1],dp[n][1][2])))));
	cout<<res<<"\n";
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 25 ms 27812 KB Output is correct
8 Correct 35 ms 27808 KB Output is correct
9 Correct 35 ms 27812 KB Output is correct
10 Correct 33 ms 27808 KB Output is correct
11 Correct 33 ms 27760 KB Output is correct
12 Correct 25 ms 27748 KB Output is correct
13 Correct 27 ms 27812 KB Output is correct
14 Correct 31 ms 27816 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Incorrect 0 ms 348 KB Output isn't correct
17 Halted 0 ms 0 KB -