oj.uz

답안 #210833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
210833 2020-03-18T19:10:16 Z amiratou Lamps (JOI19_lamps) C++14
4 / 100
 106 ms 45644 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 t[1000002],pre[1000002],dp[1000002];
int n;
string A,B;
void pro(){
	for (int i = n-1; i >= 0; i--)
	{
		int h=(int)(A[i]-'0')^(int)(B[i]-'0');
		if(!h)t[i]=-1;
		else if(i==(n-1)||t[i+1]==-1)t[i]=i;
		else t[i]=t[i+1];
		if(i==(n-1)||(B[i]!=B[i+1]))pre[i]=i;
		else pre[i]=pre[i+1];
		//dp[i+1]=INF;
	}
}
int solve(int idx){
	if(idx==n)
		return 0;
	if(dp[idx]!=-1)
		return dp[idx];
	int ans=INF;
	if(A[idx]==B[idx])
		ans=min(ans,solve(idx+1));
	else{
		ans=min(ans,solve(t[idx]+1)+1);
		ans=min(ans,solve(pre[idx]+1)+1);
	}
	return dp[idx]=ans;
}
/*int solve(){
	dp[0]=0;
	for (int i = 0; i < n; ++i)
	{
		if(A[i]==B[i])dp[i+1]=min(dp[i+1],dp[i]);
		else{
			dp[t[i]+1]=min(dp[t[i]+1],dp[i]+1);
			dp[pre[i]+1]=min(dp[pre[i]+1],dp[i]+1);
		}
	}
	return dp[n];
}*/
int32_t main(){
	boost;
	//freopen(".in","r",stdin);
	cin>>n;
	cin>>A>>B;
	pro();
	memset(dp,-1,sizeof dp);
	int ans=solve(0);
	for (int i = 0; i < n; ++i)
		A[i]=(char)(1-(int)(A[i]-'0')+'0'),pre[i]=t[i]=0;
	pro();
	memset(dp,-1,sizeof dp);
	cout<<min(ans,solve(0)+1);
	return 0;
}
//long long
//array bounds
//special cases
//binary search

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4220 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 9 ms 4216 KB Output is correct
5 Correct 10 ms 4216 KB Output is correct
6 Correct 11 ms 4348 KB Output is correct
7 Correct 9 ms 4216 KB Output is correct
8 Correct 10 ms 4344 KB Output is correct
9 Correct 9 ms 4344 KB Output is correct
10 Correct 9 ms 4216 KB Output is correct
11 Correct 10 ms 4344 KB Output is correct
12 Correct 9 ms 4344 KB Output is correct
13 Incorrect 8 ms 4216 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4220 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 9 ms 4216 KB Output is correct
5 Correct 10 ms 4216 KB Output is correct
6 Correct 11 ms 4348 KB Output is correct
7 Correct 9 ms 4216 KB Output is correct
8 Correct 10 ms 4344 KB Output is correct
9 Correct 9 ms 4344 KB Output is correct
10 Correct 9 ms 4216 KB Output is correct
11 Correct 10 ms 4344 KB Output is correct
12 Correct 9 ms 4344 KB Output is correct
13 Incorrect 8 ms 4216 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 4216 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 10 ms 4372 KB Output is correct
5 Correct 10 ms 4216 KB Output is correct
6 Correct 9 ms 4220 KB Output is correct
7 Correct 75 ms 45512 KB Output is correct
8 Correct 106 ms 45640 KB Output is correct
9 Correct 98 ms 45512 KB Output is correct
10 Correct 101 ms 45516 KB Output is correct
11 Correct 100 ms 45644 KB Output is correct
12 Correct 76 ms 45588 KB Output is correct
13 Correct 63 ms 31948 KB Output is correct
14 Correct 71 ms 30288 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 4220 KB Output is correct
2 Correct 9 ms 4216 KB Output is correct
3 Correct 9 ms 4216 KB Output is correct
4 Correct 9 ms 4216 KB Output is correct
5 Correct 10 ms 4216 KB Output is correct
6 Correct 11 ms 4348 KB Output is correct
7 Correct 9 ms 4216 KB Output is correct
8 Correct 10 ms 4344 KB Output is correct
9 Correct 9 ms 4344 KB Output is correct
10 Correct 9 ms 4216 KB Output is correct
11 Correct 10 ms 4344 KB Output is correct
12 Correct 9 ms 4344 KB Output is correct
13 Incorrect 8 ms 4216 KB Output isn't correct
14 Halted 0 ms 0 KB -