# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
210833 |
2020-03-18T19:10:16 Z |
amiratou |
Lamps (JOI19_lamps) |
C++14 |
|
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
# |
Verdict |
Execution time |
Memory |
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 |
- |
# |
Verdict |
Execution time |
Memory |
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 |
- |
# |
Verdict |
Execution time |
Memory |
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 |
# |
Verdict |
Execution time |
Memory |
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 |
- |