oj.uz

답안 #211157

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
211157 2020-03-19T10:36:38 Z amiratou Lamps (JOI19_lamps) C++14
4 / 100
 120 ms 106312 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define rando mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define fi first
#define se second
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define debugii(x) cerr << " - " << #x << ": " << x.fi<<","<<x.se << endl;
#define sep() cerr << "--------------------" << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ld long double
#define ll long long
//#define int ll
#define ii pair<int,int>
#define v vector<int>
#define vii vector<ii>
#define vv vector<vector<int> >
#define mp make_pair
#define INF 1000000000
#define pb push_back
#define EPS 1e-9
const int MOD = 1000000007; // 998244353
int dp[1000006][2][3],n;
string A,B;
char conv(char a,int t,int s){
	if(t)a=(char)(1-(int)(a-'0')+'0');
	if(!s)a='0';
	if(s==1)a='1';
	return a;
}
int solve(int idx,int t,int s){
	if(idx==n)
		return 0;
	if(dp[idx][t][s]!=-1)
		return dp[idx][t][s];
	int ans=INF;
	for (int i = 0; i < 2; ++i)
		for (int j = 0; j < 3; ++j)
		{
			int cost=0;
			cost+=(i?(i!=t):0)+((j!=2)?(j!=s):0);
			if(conv(A[idx],i,j)!=B[idx])continue;
			ans=min(ans,solve(idx+1,i,j)+cost);
		}
	return dp[idx][t][s]=ans;
}
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	memset(dp,-1,sizeof dp);
	cin>>n>>A>>B;
	cout<<solve(0,0,2);
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Subtask #1
0 / 6.0

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

Subtask #2
0 / 41.0

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

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 17 ms 23808 KB Output is correct
3 Correct 16 ms 23808 KB Output is correct
4 Correct 17 ms 23808 KB Output is correct
5 Correct 16 ms 23808 KB Output is correct
6 Correct 16 ms 23808 KB Output is correct
7 Correct 108 ms 106184 KB Output is correct
8 Correct 116 ms 106188 KB Output is correct
9 Correct 112 ms 106312 KB Output is correct
10 Correct 120 ms 106244 KB Output is correct
11 Correct 111 ms 106188 KB Output is correct
12 Correct 112 ms 106184 KB Output is correct
13 Correct 110 ms 106184 KB Output is correct
14 Correct 110 ms 106188 KB Output is correct

Subtask #4
0 / 49.0

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